好奇怪,你为什么能插队 优先级队列 堆
小吃街卖烤鸡爪的好多人排队,不知道是不是真的好吃,反正从来没买到过,排队估计得半个多小时,好想插队。
不知道大家有没有遇到过这个面试题
给定一个很大的数据量n,要求从n中提取出最大/最小/重复频度最高的N个数(N相对于n较小,如n为10亿量级,而N为100)。
想到这个题,我就想起2年前,坐在电脑前面,诺手一个大杀四方,五连批喷他Q,我眼睁睁看着基地被对面诺手推掉。
啊?诺手不是你啊?
跑题了,想到这个题我就想起了优先级队列,想起优先级队列我就想起二叉堆了。
二叉堆分为最大堆和最小堆。见名知意,堆就是像金字塔那样的小土丘,上面尖,下面胖。
最大堆就是根节点(堆的尖尖)的值最大,再往下每个子节点的值都比父节点的值小。反过来最小堆就是根节点的值最小,再往下每个子节点的值都比父节点的值大。
二叉堆的另一个性质:堆是一个完全二叉树(叶子节点只在最后两层,若最后一层不全,那么叶子结点都靠左对齐)。
上图就是一个最小堆
为了能维护一个二叉堆有两个核心操作
- 上滤
- 下滤
上滤
有一个数组[3,5,6],用二叉树表示是这样
现在插入一个元素[2],变为[3,5,6,2]。
若还想要满足最小堆父节点的值小于子节点的值的特性,那么就需要把2提上去,把5替换下来,变成这样。
同样的,需要把2提上去替换3。数组就变成了[2,3,6,5]
这个过程就叫做上滤。
我们用代码的逻辑分析一下:若有一个新的节点,那么需要比较它的父节点,若新节点的值小于父节点的值,把他们两个进行交换。同样的,若交换完成后,新节点的值仍小于父节点的值,继续交换。
在这过程中,也不必真正的交换父子两个节点的值,因为新节点的值还要继续进行下一轮判断,最后赋值即可
那么逻辑就清楚了,简单实现一下
public void siftUp(int[] array){
//新节点的下标
int newIndex = array.length-1;
//父节点的下标
int parentIndex = (newIndex - 1) / 2;
//新节点的值
int newValue = array[newIndex];
//如果还有父节点,且当前节点的值小于父节点的值,就继续向上
while(newIndex>0 && newValue < array[parentIndex]){
//把父节点的值下放
array[newIndex] = array[parentIndex];
//把当前节点下标赋值为父节点下标,然后继续向上循环
newIndex = parentIndex;
parentIndex = (parentIndex - 1 ) /2;
}
//赋值新节点的值
array[newIndex] = newValue;
}
下滤
下滤操作一般是在从二叉树构建堆、删除节点时使用的
删除节点时的下滤
现有数组[2,3,6,5]
删除堆顶节点2,为了维护二叉树,把末尾节点5提到堆顶,变为[5,3,6]
若还想要满足最小堆父节点的值小于子节点的值的特性,需要把节点5下滤。那么用3和6的哪个呢?当然是更小的那个。我们把5下滤,把3提上来。变为[3,5,6]
这个过程就叫做下滤。
我们用代码的逻辑分析一下:若删除一个节点,或二叉树本身不符合堆的性质,那么需要比较节点与子节点的值,找出两个子节点中最小的节点,把他们两个进行交换。若交换后节点仍大于子节点,继续交换。
在这过程中,也不必真正的交换父子两个节点的值,因为新节点的值还要继续进行下一轮判断,最后赋值即可
那么逻辑就清楚了,简单实现一下
/**
* 下滤
* @param array 数组
* @param parentIndex 父节点下标
* @param length 数组长度
*/
public void siftDown(int[] array, int parentIndex, int length) {
int parentValue = array[parentIndex];
//左子节点的下标
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
//如果有右子节点,比较左右节点的值,如果右子节点小于左子节点,那么更新childIndex为右子节点的下标
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
//判断父节点是否大于左右子节点的最小值,若大于,则需要下滤,否则直接跳出循环
if (parentValue > array[childIndex]) {
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
} else {
break;
}
}
//赋值父节点的值
array[parentIndex] = parentValue;
}
构建堆
对于一个二叉树,把它构建成最小堆,只需要对每个父节点下滤即可。
private void heapify(int[] array) {
//从最后一个父节点开始下滤
for (int i = (array.length / 2) - 1; i >= 0; i--) {
siftDown(array, i, array.length);
}
}
堆排序
从上面删除节点的下滤操作可以看出,每次最小堆的堆顶元素都是当前数组里最小的。这样虽然堆维护的数组不是有序的,但通过删除堆顶节点也能获取到有序的数组了。
public void heapSort(int[] array) {
//建堆
heapify(array);
//循环把堆顶元素放到最后,相当于删除堆顶元素
for (int i = array.length - 1; i >= 0; i--) {
//交换堆顶和最后一个元素
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
//下滤新节点,使堆顶元素最小,第三个参数是数组的长度,每次都减少一个,相当于数组删除了堆顶元素
siftDown(array, 0, i);
}
}
关于堆中操作的时间复杂度如下:
二叉堆插入节点、删除节点的复杂度都是O(logn),但对于一个乱序的二叉树,自底向上的下滤构建二叉堆的时间复杂度是近似于O(n)的。
关于时间复杂度大家可以自己分析一下。
PriorityQueue
在java中堆的实现是PriorityQueue,也就是优先级队列。建议大家在了解PriorityQueue的用法的同时,也学会怎么自己实现一个堆。有些公司在问关于堆相关的问题时,会明确告诉你不能使用PriorityQueue,这时就需要自己实现一个简单的堆啦。平常用的时候当然还是使用PriorityQueue更方便。
关于PriorityQueue的源码,大家可以自己看一下,总的来说就是对数组的上滤、下滤保持堆的特性,同样的PriorityQueue也会有对数组的扩容等操作,方便我们使用。
PriorityQueue默认实现是最小堆。作为一个队列也具有offer()、peek()、poll()等函数。
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(3);
priorityQueue.offer(5);
priorityQueue.offer(1);
System.out.println(priorityQueue);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.peek());
System.out.println(priorityQueue);
}
运行结果:
[1, 5, 3]
1
3
[3, 5]
哈哈,刚才做算法题因为不会堆气晕过去了,没想到大家聊了这么多啊。
既然明白了堆的定义,那我们就来一道题练练手,熟悉一下API(堆)的使用
347. 前 K 个高频元素
题目:
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
题解
堆用来解决求top N的问题十分方便。对这个题,我们只需要建立一个堆,出现次数多的优先级高就好啦。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//计算元素的出现次数
Map<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//建立优先级队列,出现次数少的优先级高,即最小堆
//为了方便存储元素和元素的出现次数,这里用数组表示,下标0表示元素,下标1表示出现次数
PriorityQueue<int[]> priority = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int key = entry.getKey();
int count = entry.getValue();
//我们不必把所有元素都放入队列,只放k个即可
//因为是最小堆,堆顶的出现次数一定最小,只要出现次数比堆顶的多,就代替堆顶元素
if(priority.size()>=k){
//拿到堆顶元素
int[] peek = priority.peek();
//判断是否比堆顶元素的出现次数多
if(count > peek[1]){
//替换堆顶
priority.poll();
priority.offer(new int[]{key,count});
}
}else{
//优先级队列中没有达到k个元素,直接放入队列,即前k个
priority.offer(new int[]{key,count});
}
}
//此时大小为k的优先级队列中即是出现频率前k高的元素,取出返回即可
int[] res = new int[k];
int i = 0;
while(!priority.isEmpty()){
res[i++] = priority.poll()[0];
}
return res;
}
}
最后,我觉得在生活中尽量不要使用特权,使用特权的就可能有人受伤,如果想过把特权的瘾,整几个优先级队列,把优先级弄得高高的。就像对象也不一定要在现实中存在,用程序new就行啦,想要几个对象要几个~
以上都是学习或工作中的感悟,希望文章能有幸帮助到你。如有错误请指出,感谢。
转载自:https://juejin.cn/post/7238541391654993977