好奇怪，你为什么能插队优先级队列堆

叁歲伎倆 2023-10-11 23:40 14阅读 0赞

小吃街卖烤鸡爪的好多人排队，不知道是不是真的好吃，反正从来没买到过，排队估计得半个多小时，好想插队。

不知道大家有没有遇到过这个面试题

给定一个很大的数据量n，要求从n中提取出最大/最小/重复频度最高的N个数（N相对于n较小，如n为10亿量级，而N为100）。

想到这个题，我就想起2年前，坐在电脑前面，诺手一个大杀四方，五连批喷他Q，我眼睁睁看着基地被对面诺手推掉。

啊？诺手不是你啊？

![format_png][]

跑题了，想到这个题我就想起了优先级队列，想起优先级队列我就想起二叉堆了。

二叉堆分为最大堆和最小堆。见名知意，堆就是像金字塔那样的小土丘，上面尖，下面胖。

最大堆就是根节点(堆的尖尖)的值最大，再往下每个子节点的值都比父节点的值小。反过来最小堆就是根节点的值最小，再往下每个子节点的值都比父节点的值大。

二叉堆的另一个性质：堆是一个完全二叉树(叶子节点只在最后两层，若最后一层不全，那么叶子结点都靠左对齐)。

![format_png 1][]

上图就是一个最小堆

为了能维护一个二叉堆有两个核心操作

*  上滤
 *  下滤

# 上滤 #

有一个数组\[3,5,6\]，用二叉树表示是这样

![format_png 2][]

现在插入一个元素\[2\]，变为\[3,5,6,2\]。

![format_png 3][]

若还想要满足最小堆父节点的值小于子节点的值的特性，那么就需要把2提上去，把5替换下来，变成这样。

![format_png 4][]

同样的，需要把2提上去替换3。数组就变成了\[2,3,6,5\]

![format_png 5][]

这个过程就叫做上滤。

我们用代码的逻辑分析一下：若有一个新的节点，那么需要比较它的父节点，若新节点的值小于父节点的值，把他们两个进行交换。同样的，若交换完成后，新节点的值仍小于父节点的值，继续交换。

在这过程中，也不必真正的交换父子两个节点的值，因为新节点的值还要继续进行下一轮判断，最后赋值即可

那么逻辑就清楚了，简单实现一下

java复制代码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\]

![format_png 6][]

删除堆顶节点2，为了维护二叉树，把末尾节点5提到堆顶，变为\[5,3,6\]

![format_png 7][]

若还想要满足最小堆父节点的值小于子节点的值的特性，需要把节点5下滤。那么用3和6的哪个呢？当然是更小的那个。我们把5下滤，把3提上来。变为\[3,5,6\]

![format_png 8][]

这个过程就叫做下滤。

我们用代码的逻辑分析一下：若删除一个节点，或二叉树本身不符合堆的性质，那么需要比较节点与子节点的值，找出两个子节点中最小的节点，把他们两个进行交换。若交换后节点仍大于子节点，继续交换。

在这过程中，也不必真正的交换父子两个节点的值，因为新节点的值还要继续进行下一轮判断，最后赋值即可

那么逻辑就清楚了，简单实现一下

java复制代码 /**
     * 下滤
     * @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;
    }

# 构建堆 #

对于一个二叉树，把它构建成最小堆，只需要对每个父节点下滤即可。

java复制代码    private void heapify(int[] array) {
            //从最后一个父节点开始下滤
            for (int i = (array.length / 2) - 1; i >= 0; i--) {
                siftDown(array, i, array.length);
            }
        }

# 堆排序 #

从上面删除节点的下滤操作可以看出，每次最小堆的堆顶元素都是当前数组里最小的。这样虽然堆维护的数组不是有序的，但通过删除堆顶节点也能获取到有序的数组了。

java复制代码    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()等函数。

java复制代码    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);
        }

运行结果：

csharp复制代码[1, 5, 3]
    1
    3
    [3, 5]

哈哈，刚才做算法题因为不会堆气晕过去了，没想到大家聊了这么多啊。

![format_png 9][]

既然明白了堆的定义，那我们就来一道题练练手，熟悉一下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的问题十分方便。对这个题，我们只需要建立一个堆，出现次数多的优先级高就好啦。

java复制代码    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就行啦，想要几个对象要几个~

[format_png]: https://img-blog.csdnimg.cn/img_convert/9fe138e6a88df048697797a9b7749208.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/9a18097fa0afc8ea4efdeea9d8c481a9.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/b67594585b124233a3e7e22a981ddcdd.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/a82dc0c783c4173b09829f10588cffad.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/fcbd3f2b6b119e8fde927605155475b4.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/bdec238b87758b8e087abb8dea5d4c06.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/03f3d26dec62cb860a4167620bc3f4c9.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/ffd2d153225a4282c3536e586a271c01.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/927d80b4ffbb2fd85aa4e1cc9fc0f075.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/bf7c3b7f41f2aee19de3af08c6950680.webp?x-oss-process=image/format,png