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;
            }
        }
    }

📃建堆算法

该部分稍作理解即可：

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

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

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

推荐使用向下建堆，因为后续的堆排序和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)