堆的应用--优先队列
01
什么是堆
Law
1. 堆是一种树，由它实现的优先级队列的插入和删除的时间复杂度都是O(logn)，用堆实现的优先级队列虽然和数组实现相比较删除慢了些，但插入的时间快的多了。当速度很重要且有很多插入操作时，可以选择堆来实现优先级队列。
2. java的堆和数据结构堆：java的堆是程序员用new能得到的计算机内存的可用部分。而数据结构的堆是一种特殊的二叉树。
3. 堆是具有如下特点的二叉树：
3.1 它是完全二叉树，也就是说除了树的最后一层节点不需要是满的，其他的每一层从左到右都必须是满的。
3.2 它常常用数组实现。
3.3 堆中每一个节点都满足堆的条件，也就是说每一个关键字的值都大于或等于这个节点的子节点的关键字值。
4. 堆在存储器中的表示是数组，堆只是一个概念上的表示。
5. 堆的弱序：堆和二叉搜索树相比是弱序的，在二叉搜索树中，当前节点的值总是比左子节点的值大，却比它的右子节点的值小，因此按序遍历相对容易。而堆的组织规则弱，它只要求从根到叶子节点的每一条路径，节点都是按降序排列的。同一节点的左右子节点都没有规律。因此，堆不支持按序遍历，也不能在堆上便利的查找指定关键字，因为在查找的过程中，没有足够的信息决定选择通过节点的两个那一个走向下一层。它也不能在少于O(logn)的时间内删除一个指定的节点，因为没有办法找到这个节点。因此，堆的这种近乎无序的规则似乎毫无用处，不过对于快速移除最大节点的操作，以及快速插入新节点的操作，这种顺序已经足够了。这些操作是使用堆作为优先级队列所需要的全部操作。
6. 移除操作：移除是指删掉关键字值最大的节点，即根节点。移除思路如下：
6.1.移走根，
6.2.把左后一个节点移到根的位置，
6.3.一直向下筛选这个节点，知道它在一个大于它的节点之下，小于它的节点之上为止。
6.4 说明：在被筛选节点的每个暂时停留的位置，向下筛选的算法总是要检查那一个子节点更大，然后目标节点和较大的子节点交换位置，如果要把目标节点和较小的子节点交换，那么这个子节点就会变成大子节点的父节点，这就违背了堆的条件。
7.堆的插入：插入使用向上筛选，节点最后插入到数组最后第一个空着的单元中，数组容量大小增加1。
7.1 说明：向上筛选的算法比向下筛选的算法相对简单，因为它不需要比较两个子节点关键字值的大小，节点只有一个父节点。目标节点主要和它的父亲节点换位即可。
7.2.不是真的交换：
02
优先队列
Law
优先队列的特点:
能保证每次取出的元素都是队列中优先级别最高的. 优先级别可以是自定义的, 例如, 数据的数值越大, 优先级越高, 或者数据的值越小, 优先级越高, 优先级别甚至可以通过各种负责的计算得到.
应用场景:
从一堆堆杂乱无章的数据当中按照一定的顺序, 逐步的筛选出部分乃至全部的数据
举例 : 任意一个数组, 找到前k大的数
解法1:
先对数组排序, 然后依次输出前k大的数, 自幅度将会是O(nlogn)
解法2:
使用优先队列, 复杂度优化成O(k + nlogk)
当数据量很大的时候, 即n特别大, 而k相对较小的时候, 显然, 利用优先队列能有效的降低算法复杂度. 因为要找到前k大的数, 并不需要所有的数进行排序
实现:
优先队列的本质是一个二叉堆结构, 堆在英文中叫Binary Heap, 它是利用一个数组结构来实现的完全二叉树, 换句话说, 优先队列的本质是一个数组, 数组里面的每个元素既有可能是其他元素的父节点, 也有可能是其他元素的节点, 而且, 每个父节点只能有连个子节点, 很像一颗二叉树的结构.
牢记下面优先队列的三个重要性质
1. 数组里面的第一个元素array[0]拥有最高的优先级别.
2. 对于一个下标i, 那么对于元素array[i] 而言:
2.1 它的父节点所对应的元素下标是(i -1) / 2
2.2 它的左孩子所对应的元素下标是2 * i + 1
2.3它的右孩子所对应的元素下标是 2 * i+ 2
3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别.
03
例题分析
Law
347: 前K个高频元素
给定一个非空的整数数组, 返回其中出现评率前K高的元素
给定一个非空的整数数组, 返回其中出现评率前K高的元素
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
官网给出的解法
k = 1 时问题很简单，线性时间内就可以解决。只需要用哈希表维护元素出现频率，每一步更新最高频元素即可。
当 k > 1 就需要一个能够根据出现频率快速获取元素的数据结构，这就是优先队列。
首先建立一个元素值对应出现频率的哈希表。在 Java 中使用 HashMap，但需要手工填值。在 Python 中提供一个字典结构用作哈希表和在 collections 库中的 Counter 方法去构建我们需要的哈希表。
这个步骤需要 O(N) 时间其中 N 是列表中元素个数。
第二步建立堆，堆中添加一个元素的复杂度是 O(log(k))，要进行 N 次复杂度是 O(N)。
最后一步是输出结果，复杂度为 O(klog(k))。
在 Python 中可以使用 heapq 库中的 nlargest 方法，可以在相同时间内完成，但只需要一行代码解决。
代码
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer,Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 遍历map，用最小堆保存频率最大的k个元素, 保证最上面的元素时最小的元素
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (Integer key : map.keySet()) {
pq.add(key);
if (pq.size() > k) {
// 当元素的个数超k个, 我们就把最小, 即队列开头的元素删除掉
pq.poll();
}
}
// 取出堆中的元素
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
}
python的解法:
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
04
自己的分析
Law
如果是我自己来做的话, 这个题目的使用类型正好适合redis的sort set的数据类型, 我们直接使用redis就可以解决了, 如果你对redis的使用有任何疑问, 可以参考我原来写过的一篇文章, redis的专题, 帮你解决任何redis的问题;
扫描二维码
关注我们
微信号 : stormling
头条号：故事凌