共计 4208 个字符，预计需要花费 11 分钟才能阅读完成。
上一篇的「Java 汇合框架」里，还剩下一个大问题没有说的，那就是 PriorityQueue，优先队列，也就是堆，Heap。
什么是堆？
堆其实就是一种非凡的队列——优先队列。
一般的队列游戏规则很简略：就是先进先出；但这种优先队列 搞非凡 ，不是依照进队列的工夫程序，而是依照每个元素的 优先级 来比拼，优先级高的在堆顶。
这也很容易了解吧，比方各种软件都有会员制度，某软件用了会员就能减速下载的，不同等级的会员速度还不一样，那就是优先级不同呀。
还有其实每个人回复微信音讯也是默默的把音讯放进堆里排个序：先回男朋友女朋友的，而后再回其他人的。
这里要区别于操作系统里的那个“堆”，这两个尽管都叫堆，然而没有半毛钱关系，都是借用了 Heap 这个英文单词而已。
咱们再来回顾一下「堆」在整个 Java 汇合框架中的地位：
也就是说，
- PriorityQueue 是一个类 (class)；
- PriorityQueue 继承自 Queue 这个接口 (Interface)；
<span style=”display:block;color:blue;”> 那 heap 在哪呢？
heap 其实是一个 形象的数据结构 ，或者说是 逻辑上的数据结构，并不是一个物理上实在存在的数据结构。
<span style=”;color:blue;”>heap 其实有很多种实现形式，</span> 比方 binomial heap, Fibonacci heap 等等。然而面试最常考的，也是最经典的，就是 binary heap 二叉堆 ，也就是用一棵 齐全二叉树 来实现的。
<span style=”display:block;color:blue;”> 那齐全二叉树是怎么实现的？
其实是用 数组 来实现的！
所以 binary heap/PriorityQueue 实际上是用 数组 来实现的。
这个数组的排列形式有点特地，因为它总会保护你定义的（或者默认的）优先级最高的元素 在数组的首位，所以不是轻易一个数组都叫「堆」，实际上，它在你心里，应该是一棵「齐全二叉树」。
这棵齐全二叉树，只存在你心里和各大书本上；理论在在内存里，哪有什么树？就是数组罢了。
那为什么齐全二叉树能够用数组来实现？是不是所有的树都能用数组来实现？
这个就波及齐全二叉树的性质了，咱们下一篇会细讲，简略来说，因为齐全二叉树的定义要求了它在层序遍历的时候没有气泡，也就是间断存储的，所以能够用数组来寄存；第二个问题当然是否。
堆的特点
- 堆是一棵齐全二叉树；
- 堆序性 (heap order): 任意节点都 优于 它的 所有孩子。
a. 如果是任意节点都 大于 它的所有孩子，这样的堆叫 大顶堆，Max Heap;
b. 如果是任意节点都 小于 它的所有孩子，这样的堆叫 小顶堆，Min Heap;
左图是小顶堆，能够看出对于每个节点来说，都是小于它的所有孩子的，留神是 所有孩子，包含孙子，曾孙 …
- 既然堆是用数组来实现的，那么咱们能够找到每个节点和它的父母 / 孩子之间的关系，从而能够间接拜访到它们。
比方对于节点 3 来说，
- 它的 Index = 1，
- 它的 parent index = 0,
- 左孩子 left child index = 3,
- 右孩子 right child index = 4.
能够演绎出如下法则：
- 设以后节点的 index = x,
- 那么 parent index = (x-1)/2,
- 左孩子 left child index = 2*x + 1,
- 右孩子 right child index = 2*x + 2.
有些书上可能写法稍有不同，是因为它们的数组是从 1 开始的，而我这里数组的下标是从 0 开始的，都是能够的。
这样就能够从任意一个点，一步找到它的孙子、曾孙子，真的太不便了，在后文讲具体操作时大家能够更粗浅的领会到。
基本操作
任何一个数据结构，无非就是增删改查四大类：
| 性能 | 办法 | 工夫复杂度 |
|---|---|---|
| 增 | offer(E e) | O(logn) |
| 删 | poll() | O(logn) |
| 改 | 无间接的 API | 删 + 增 |
| 查 | peek() | O(1) |
这里 peek() 的工夫复杂度很好了解，因为堆的用处就是可能疾速的拿到一组数据里的最大 / 最小值，所以这一步的工夫复杂度肯定是 O(1) 的，这就是堆的意义所在。
那么咱们具体来看 offer(E e) 和 poll() 的过程。
offer(E e)
比方咱们新加一个 0 到方才这个最小堆外面：
那很显著，0 是要放在最下面的，可是，间接放上去就不是一棵齐全二叉树了啊。。
所以说，
- 咱们先保障加了元素之后这棵树还是一棵齐全二叉树，
- 而后再通过 swap 的形式进行微调，来满足堆序性。
这样就保障 满足了堆的两个特点 ，也就是保障了退出新元素之后 它还是个堆。
那具体怎么做呢：
Step 1.
先把 0 放在最初接上，别一上来就想着上位；
OK！总算先上岸了，而后咱们再一步步往上走。
这里「是否往上走」的规范在于：
是否满足堆序性。
也就是说，当初 5 和 0 之间不满足堆序性，那么替换地位，换到直到满足堆序性为止。
这里对于最小堆来说的堆序性，就是 小的数要在下面。
Step 2. 与 5 替换
此时 0 和 3 不满足堆序性了，那么再替换。
Step 3. 与 3 替换
还不行，0 还比 1 小，所以持续换。
Step 4. 与 1 替换
OK！这样就换好了，一个新的堆诞生了～
总结一下这个办法：
先把新元素退出数组的开端，再通过一直比拟与 parent 的值的大小，决定是否替换，直到满足堆序性为止。
这个过程就是 siftUp()，源码如下：
工夫复杂度
这里不难发现，其实咱们只替换了一条支路上的元素，
也就是最多替换 O(height) 次。
那么对于齐全二叉树来说，除了最初一层都是满的，O(height) = O(logn)。
所以 offer(E e) 的工夫复杂度就是 O(logn) 啦。
poll()
poll() 就是把最顶端的元素拿走。
对了，没有方法拿走两头的元素，毕竟要 VIP 先进来，小弟能力进来。
那么最顶端元素拿走后，这个地位就空了：
咱们还是先来满足堆序性，因为比拟容易满足嘛，间接从最初面拿一个来补上就好了，先放个傀儡上来。
Step1. 开端元素上位
这样一来，堆序性又不满足了，开始替换元素。
那 8 比 7 和 3 都大，应该和谁替换呢？
假如与 7 替换，那么 7 还是比 3 大，还得 7 和 3 换，麻烦。
所以是与左右孩子中 较小 的那个替换。
Step 2. 与 3 替换
上来之后，还比 5 和 4 大，那再和 4 换一下。
Step 3. 与 4 替换
OK！这样这棵树总算是稳固了。
总结一下这个办法：
先把数组的末位元素加到顶端，再通过一直比拟与左右孩子的值的大小，决定是否替换，直到满足堆序性为止。
这个过程就是 siftDown()，源码如下：
工夫复杂度
同样情理，也只替换了一条支路上的元素，也就是最多替换 O(height) 次。
所以 offer(E e) 的工夫复杂度就是 O(logn) 啦。
heapify()
还有一个赫赫有名的十分重要的操作，就是 heapify() 了，它是一个很神奇的操作，
能够用 O(n) 的工夫把一个乱序的数组变成一个 heap。
然而呢，heapify() 并不是一个 public API，看：
所以咱们没有方法间接应用。
惟一应用 heapify() 的形式呢，就是应用PriorityQueue(Collection<? extends E> c)
这个 constructor 的时候，人家会主动调用 heapify() 这个操作。
<span style=”display:block;color:blue;”> 那具体是怎么做的呢？
哈哈源码曾经裸露了：
从最初一个非叶子节点开始，从后往前做 siftDown().
因为叶子节点没必要操作嘛，曾经到了最上面了，还能和谁 swap？
举个例子：
咱们想把这个数组进行 heapify() 操作，想把它变成一个最小堆，拿到它的最小值。
那就要从 3 开始，对 3，7，5 进行 siftDown().
Step 1.
难堪 ????，3 并不必替换，因为以它为顶点的这棵小树曾经满足了堆序性。
Step 2.
7 比它的两个孩子都要大，所以和较小的那个替换一下。
替换实现后；
Step 3.
最初一个要解决的就是 5 了，那这里 5 比它的两个孩子都要大，所以也和较小的那个替换一下。
换完之后后果如下，留神并没有满足堆序性，因为 4 还比 5 小呢。
所以接着和 4 换，后果如下：
这样整个 heapify() 的过程就实现了。
好了难点来了，为什么工夫复杂度是 O(n) 的呢？
怎么计算这个工夫复杂度呢？
其实咱们在这个过程里做的操作无非就是替换替换。
那到底替换了多少次呢？
没错，替换了多少次，工夫复杂度就是多少。
那咱们能够看进去，其实 同一层的节点 最多替换的次数都是雷同的。
那么这个总的替换次数 = 每层的节点数 * 每个节点最多替换的次数
这里设 k 为层数，那么这个例子里 k=3.
每层的节点数是从上到下以指数增长：
$$\ce{1, 2, 4, …, 2^{k-1}}$$
每个节点替换的次数，
从下往上就是：
$$ 0, 1, …, k-2, k-1 $$
那么总的替换次数 S(k) 就是两者相乘再相加：
$$S(k) = \left(2^{0} *(k-1) + 2^{1} *(k-2) + … + 2^{k-2} *1 \right)$$
这是一个等比等差数列，规范的求和形式就是 错位相减法。
那么
$$2S(k) = \left(2^{1} *(k-1) + 2^{2} *(k-2) + … + 2^{k-1} *1 \right)$$
两者相减得：
$$S(k) = \left(-2^{0} *(k-1) + 2^{1} + 2^{2} + … + 2^{k-2} + 2^{k-1} \right)$$
化简一下：
（不好意思我切实受不了这个编辑器了。。。
所以 heapify() 工夫复杂度是 O(n).
以上就是堆的三大重要操作，最初一个 heapify() 尽管不能间接操作，然而堆排序中用到了这种思路，之前的「抉择排序」那篇文章里也提到了一些，感兴趣的同学能够后盾回复「抉择排序」取得文章～至于堆排序的具体实现和利用，以及为什么理论生产中并不爱用它，咱们之后再讲。
最初再说一点题外话，最近发现了几篇搬运我的文章到其余平台的景象。每篇文章都是我精心打造的，都是本人的心肝宝贝，看到他人间接搬运过来也没有表明作者和起源出处切实是太难受了。。为了最好的浏览体验，文中的图片我都没有加水印，但这也不便了别人搬运。明天思考再三，还是不想违反本人的本意，毕竟我的读者更为重要。
所以如果之后有小伙伴看到了，恳请大家后盾或者微信通知我一下呀，非常感谢！
我在各大平台同名，请认准「码农田小齐」～
如果你喜爱我的文章或者有播种的话，麻烦给我点个「赞」或者「在看」给我个小激励呀，会让我开心良久～
想跟我一起玩转算法和面试的小伙伴，记得关注我，我是小齐，咱们下期见。
