数据结构（Java）：优先级队列(堆)&堆的模拟实现&PriorityQueue集合

向下调整算法

向下调整算法：选出其左右孩子中值较小值元素（建大堆就选较大元素，建小堆就选较小元素，这里以建小堆为例），将这个元素和根节点进行比较，若比根节点还小，就和根节点交换，交换后可能导致子树不满足堆的性质，因此需要继续向下调整。

注意：向下调整算法的使用，必须要求其左右子树必须为大根堆或者小根堆！！！

向下调整算法的时间复杂度为：O（logN），因为最坏情况是从根一路比较到叶子，比较的次数即为完全二叉树的高度次。

3.1.1 向下调整算法建完整堆

我们给出一组数据：{ 27,15,19,18,28,34,65,49,25,37 }，要想将这组数据建成堆，我们可以使用向下调整法建堆。

而一组乱序数据其左右子树是不为堆的，那就需要通过向下调整算法从倒数第一个非叶子节点（下标为（数组.length-1-1)/2 ）开始建堆，直到将整棵树建成堆。

建堆的时间复杂度为：O（N）！！！，

为什么不是O（N*logN）呢？这里给出解释：

注：下文中代码实现的为大堆

向下调整整体建堆代码：

/**
     * 建堆整体时间复杂度：O（N）
     */
    public void createHeap() {
        //从倒数第一个飞非叶子节点开始建堆
        int parent = (this.usedSize - 1 - 1)/2;
        while (parent >= 0) {//O（N）
            siftDown(parent,this.usedSize);
            parent--;
        }
    }
    /**
     *向下调整算法
     * 时间复杂度：O（logN）
     * @param parent 向下调整的起始位置，即根节点
     * @param usedSize 标定调整的结束 若算出的孩子节点坐标>=usedSize时，说明已调整完成
     */
    private void siftDown(int parent, int usedSize) {
        int child = parent*2+1;
        //当没有孩子节点时，说明向下调整完成
        while (child < usedSize) {
            //当右孩子存在时，选出左右孩子的最大值（建大堆）
            if (child + 1 < usedSize) {
                if (elem[child] < elem[child + 1]) {
                    child = child + 1;
                }
            }
            //和根节点进行比较
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);
                parent = child;
                child = parent*2+1;
            }else {
                //若根节点大，说明已是大堆，break结束
                break;
            }
        }
    }

3.2 堆的插入

插入数据总共有两个步骤：

将新元素插入堆的末尾（插入后不再为堆）
使用向上调整算法调整为堆

3.2.1 向上调整算法

（这里以建小堆为例）：将元素插入到堆的末尾后，和根节点进行比较，如果比根节点还小就和根节点换，继续向上调整，直至满足堆的性质。如果没有根节点小，说明此时已满足堆的性质，调整完成。

时间复杂度：O（logN）

插入元素代码：

/**
     * 插入元素
     * 时间复杂度：O（logN）
     * @param x：新插入元素的值
     */
    public void offer(int x) {
        if (isFull()) {
            grow();
        }
        elem[usedSize] = x;
        siftUp(usedSize);
        usedSize++;
    }

    /**
     * 向上调整算法
     * @param childIndex：新插入元素的下标
     */
    public void siftUp(int childIndex) {
        //找到新节点的父节点的下标
        int parent = (childIndex - 1)/2;
        //parent为负数时，说明调整完成（最坏）
        while (parent >= 0) {
            if (elem[parent] < elem[childIndex]) {
                swap(elem,parent,childIndex);
                childIndex = parent;
                parent = (childIndex - 1)/2;
            }else {
                break;
            }
        }
    }
    /**
     * 如果堆底层的数组满了，就扩容
     */
    private void grow() {
        this.elem = Arrays.copyOf(elem,elem.length*2);
    }

向上调整算法建堆【拓展】

故我们也可以一个一个的插入元素（使用向上调整算法）来建堆，但是不推荐，因为时间复杂度比向下调整算法建堆要大，为：O（N*logN）

其实主要原因就是：最后一层的元素是最多的，都要一个个向上调整

3.3 堆的删除

堆的删除一定删除的是堆顶元素。

故，删除元素的思想很简单，即：

将堆顶元素和堆中最后一个元素交换
将堆中有效数据个数（usedSize）减1
对堆顶元素进行向下调整（只需要调整0下标就可以了）

堆删除代码：

/**
     * 删除堆元素
     */
    public void poll() {
        if (isEmpty()) {
            //如果堆为空，返回
            return;
        }
        //交换堆顶和最后一个元素
        swap(elem,0,usedSize-1);
        //堆元素有效个数-1
        usedSize--;
        //只向下调整0下标即可
        siftDown(0,usedSize);
    }

3.4 堆排序

若要升序排列，要建大根堆；若要降序排列，就要建小根堆。

以排升序为例：若要排升序，则为大堆，排序过程如下：

将堆顶元素和堆末元素交换，有效数据个数减一（因为堆顶元素为最大值元素，此时最大值元素已来到数组末尾）
将0下标处向下调整，重新调整为大堆
继续将堆顶元素和堆末元素交换，有效数据个数减一（堆顶元素为次大值元素，此时次大值元素已来到数组末尾倒数二个位置处）
将0下标处向下调整，重新调整为大堆
重复以上过程，直至只剩一个元素的时候，此时数组已有序且为升序排列

堆排序排升序代码：

/**
     * 堆排序
     */
    public void heapSort() {
        if (isEmpty()) {
            return;
        }
        int end = usedSize-1;
        while (end > 0) {
            swap(elem,0,end);
            siftDown(0,end);
            end--;
        }
    }

4、PriorityQueue集合

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。

4.1 PriorityQueue的特点

我们知道，堆的建立和每次的插入删除数据都需要需要对堆进行调整，意味着要有可比较大小的功能。PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象（自定义类要实现Comparable接口或者提供比较器），否则会抛出ClassCastException异常。
不能插入null对象，否则会抛出NullPointerException
当元素满时，会自动扩容
插入和删除元素的时间复杂度为O（logN）（删除要向下调整，插入要向上调整，但最多调整高度次）
PriorityQueue底层使用了堆数据结构
PriorityQueue默认情况下是小堆---即每次获取的堆顶元素都是最小的元素

4.2 PriorityQueue的方法

4.3 PriorityQueue源码分析

4.3.1 成员变量

PriorityQueue的底层是堆，使用的是顺序结构来存储数据。

4.3.2 构造方法

以上的三个构造方法，实际上调用的就是带两个参数的构造方法：

第一个参数是容量的大小，若没有指定容量，那默认容量就是11
第二个参数是比较器，用户可以自定义比较器：直接实现Comparator接口，然后重写该接口中的compare方法，给出比较的功能，若没有提供那就是null

当然，我们也可以用集合传参来构造优先级队列：

4.3.3 插入方法（offer）

我们先来分析源码：

通过观察offer方法（插入数据）的底层源码，我们得出结论：

①：向上调整时，如果我们提供了比较器，就通过比较器比较；如果没有提供比较器，就通过Comparable接口的方法进行比较（比较器和Comparable两者必有其一）
②：建堆时默认建的是小堆，如果要建大堆，我们可以修改比较器或者Comparable接口中compareTo方法的内部实现

上图所分析的是使用Comparable中的方法进行比较，若使用比较器来进行比较的话，内部思想其实是一模一样的。

4.3.4 扩容方法（扩容机制）

如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容（最多就是MAX_ARRAY_SIZE）

4.4 TOP-K问题

TOP-K问题：即求数据集合中前K个最大或最小的元素，一般情况下数据量都比较大。

目前解决这个问题我们有三种思路，设共有N个数据：

将全部N个元素排序，取前K个元素
将整体N个元素建成堆，拿出堆顶元素，调整；再拿出堆顶元素，再调整......依次拿出K个元素
（求前K个最小元素）：把前K个元素建成大根堆，将堆顶元素依次和剩下的N-K个元素比较，若比堆顶元素小，就删除堆顶元素并将这个元素入堆，将剩余的元素全部比较完后，堆中的K个元素就是前K个最小元素，堆顶元素就是第K个最小元素。（建大根堆的原因就是，堆顶元素是堆中最大的，和其余N-K个元素比较后，堆中元素就是所有元素中最小的，而堆顶元素就是第K小元素）

我们分析以上三种思路的时间复杂度：

思路一：最快的排序算法也只能为：O（N*logN）

思路二：使用集合时，我们只能使用offer方法插入元素向上调整来建堆，为O（N*logN），接着依次出K个元素，每次出完都要调整，为O（K*logN），故整体为O（（N+K）*logN）

思路三：前K个元素建堆的时间复杂度为：O（K*logK），剩余N-K个元素依次比较和调整为堆的时间复杂度为：O（（N-K）*logK），故整体为：O（N*logK）

我们可以看出思路三的时间效率是最高的，所以我们可以使用思路三来解决遇见的TOP-K问题。

思路三总结：

求前K个最大元素，建小堆。
求前K个最小元素，建大堆。

4.4.1 TOP-K问题力扣OJ题

. - 力扣（LeetCode）

代码：

/**
 * 最小前K个数 ->建大堆
 */
class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = 
                new PriorityQueue<>(new Comparator<Integer>() {
            //匿名内部类 建大堆-》修改比较器方法
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

OK~本次博客到这里就结束了，

感谢大家的阅读~欢迎大家在评论区交流问题~

如果博客出现错误可以提在评论区~

创作不易，请大家多多支持~

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。