PriorityQueue其本质是一个优先级队列的集合。

1. 优先级队列

那什么是优先级队列呢？我们先从它的概念聊起。

概念：

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

2. 优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

问题又来了，什么叫做堆呢？

2.1 堆

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

这不是很好理解，我们来画个图：

我用绿色和灰色圈起来的我们将其看为一棵树，我们发现这颗树上的根节点的值都大于其左右子节点，这样的我们称之为大根堆；但如果是每棵树的根节点的值都小于其左右子节点，我们称之为小根堆。

堆的性质，我们上面已经提到了；

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一棵完全二叉树。

当然啦，从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。

如上图，我们不会存在浪费空间的情况，但是如果是一颗非完全二叉树那么就会存在浪费空间的情况：

所以：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

2.2 堆的创建

对于任意集合中的数据，如何将其创建成堆呢？

我们只需要象完全二叉树一样去插入，然后再对其向下（向下）调整即可。

具体实现还得看需求，需要小根堆则向下调整，需要大根堆则向上调整。

我们以向上调整为例：

首先先创建一个堆，代码如下：

public class TestHeap {
    public int[] elem;
    public int usedSize;//堆的有效元素数
    public TestHeap() {
        this.elem = new int[10];//初始化一个容量，后面还可以扩容
    }
}

2.3 入堆

假设有这么个堆，我们需要插入新元素98：

从逻辑结构上看这并不是一个大根堆，我们得想办法让98到68的位置上去。此时就发生了向上调整：

一次仍然得不到大根堆，继续向上调整：

再次调整后得到了一个新的大根堆。

动图演示：

那么思路整理好了，代码如何去写呢？

写代码前我们得知道几个概念：

将元素存储到数组中后，可以根据二叉树章节的性质对树进行还原。假设i为节点在数组中的下标，则有：

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2

如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子

如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

再PriorityQueue中向上调整传了一个父元素下标和一个E类型的元素，我们简单一点，只进行调整，插入元素后面的方法再写。

堆的向上调整，调整分为如下几步

1. 假设当前插入的元素处（节点）为孩子，那么需要找到他的父亲节点，计算公式为 child = (parent - 1) / 2

2. 通过所得到的父亲与孩子（都是下标），判断二者所代表的值大小，假设当前要建大堆，如果孩子比父亲大，那么就需要交换孩子与父亲的值，孩子变成父亲，向上更新父亲；如果不满足条件，则不需要进行调整，直接结束循环即可

3. 假设这个新插入的元素（节点）很大，甚至能直接取代堆顶元素（根节点），那么循环的条件就要设为孩子 > 0

代码如下：

 public void shiftUp(int parent) {
        int child = (parent - 1)/2 ;
        while (child > 0) {
            //找出左右孩子中最大的值与之交换
            if ( elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

注意：

1. 在进行向上调整时，正确的找到孩子及其对应父亲是关键

无论是左孩子还是右孩子，都可以通过 parent = (child - 1) / 2 来计算父亲

2. 调整的核心是为元素找到合适的位置（这个思想很重要）

所谓合适的位置就是必须满足原则一，成为大堆或小堆

说到这里我们又不得不提一嘴堆的时间复杂度

2.4 堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

故此：建堆的时间复杂度为O(N)

写完了向上调整，我们入堆的准备工作就结束了，可以开始正式入堆。

那么我们的代码就很简单了：

思路：

1. 第一步当然是需要检查容量是否足够，不够的话需要扩容，我们写简单一点，直接用Arrays.copyOf（）方法

2. 我们将需要添加进来的元素，直接向数组中放入就好

3. 插入元素后，它就不一定是一个大根堆了，那么我就需要给他向上调整以下即可

创建堆和插入代码：

public void createHeap() {
        //为什么不直接减2，而需要减1再减1？
        //因为usedSize - 1 是数组下标，在逻辑上我们从父节点到左子节点需要减1 / 2；
        for (int parent = (usedSize-1-1) / 2; parent >= 0; parent--) {
            shiftUp(parent,usedSize);
        }
}
//向上调整建堆的时间复杂度：N*logN
    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        shiftUp(usedSize - 1);
    }
private boolean isFull() {
        return usedSize == elem.length;
    }

2.4 出堆

出堆，出的是堆顶元素，即下标为0处的元素，因为对于数组来说，头删是十分不利的，因此我们这里学要借助一个小技巧：

将堆顶元素与堆底元素交换，然后将 size - -，这样就间接删除了原堆顶元素
元素交换后，堆的整体有序性将被打破，此时需要借助向下调整函数来矫正堆

注意：堆的删除一定删除的是堆顶元素。具体如下：

1. 将堆顶元素对堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

如图所示：

刚刚了解了啥叫向上调整那么啥叫向下调整啊？

2.4.1 向下调整

如果父亲节点大于其左右子节点，就要将左右子节点中最小的值与父亲节点进行交换；直到没有左右子节点，或者父节点小于左右子节点。

如图所示：

动图演示：

向下调整的步骤

1. 确认向下调整的父亲，这里是删除堆顶元素，所以父亲是0

2. 根据公式计算出目标孩子，假设左孩子为目标孩子，后续会进行判断验证

左孩子的计算公式 leftChild = parent * 2 + 1

右孩子的计算公式 rightChild = parent * 2 + 2

左右孩子间隔为 1，判断验证起来也很容易

3. 判断左孩子是否为目标孩子，如果不是， child + 1 修改为右孩子，是的话就用左孩子

如果左孩子为最后一个孩子，那么此时进行判断验证是非法的，因为会涉及到越界问题，因此在判断验证前，需要先判断右孩子是否存在，即 child + 1 < len

4. 判断当前孩子值与父亲值间的关系，假设建大堆，如果当前孩子值大于父亲值，那么就进行值交换，父亲变成孩子，重新假设目标孩子；如果不满足条件，跳出循环即可

5. 循环结束条件为 child < len，当 child >= len时，说明此时的父亲已经是当前堆中的最小父亲了（有孩子的才叫父亲）

代码如下：

 public void shiftDown(int parent, int len) {
        int child = 2*parent + 1;
        while (child > len) {
            //存在有右孩子的情况
            if (child + 1 > len && elem[child] < elem[child + 1]) {
                child++;
            }
            //找出左右孩子中最大的值与之交换
            if ( elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

📃建堆算法

该部分稍作理解即可：

建堆算法是指直接传入一个数组，通过这个数组生成对应的大堆（小堆），建堆的步骤如下：

开辟一块足够大的空间，作为堆空间
拷贝数组中的所有元素至新空间内
通过两种不同的方式进行堆调整

向上调整（效率低）
向下调整（效率高）

两种调整性能比对	时间复杂度	数据量：100万	数据量：1亿（无序）	数据量：1亿（有序）
向上调整建堆	F(N) = N*logN	耗时29毫秒	耗时3036毫秒	耗时2310毫秒
向下调整建堆	F(N) = N - log(N + 1)	耗时22毫秒	耗时2372毫秒	耗时1997毫秒

推荐使用向下建堆，因为后续的堆排序和Top-K用的都是向下调整

关于堆的其他操作：取堆顶元素、当前堆的有效元素数、判断堆是否为空等，都是很简单的功能，基本逻辑和顺序表一样，忘记的可以去看看以前的博客

3. 堆的应用

聊了这么多堆，那么我们究竟可以干什么呢？

3.1 PriorityQueue的实现

PriorityQueue是用堆作为底层结构封装优先级队列。

我们还有PriorityBlockingQueue。

简单来说PriorityQueue，这个Queue继承自AbstractQueue，是非线程安全的。

而PriorityBlockingQueue是一个BlockingQueue，所以它是线程安全的。

3.2 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

具体的堆排序在排序那一章节中会讲到。

更多关于堆的代码我放在了我的gitee上：

myHeap/src/TestHeap.java · wjm的码云/java - 码云 - 开源中国 (gitee.com)

PriorityQueue