文章目录

1. 1. 堆与优先队列

堆与优先队列

---

堆化

堆化就是调整数组中的数据，使之符合堆的定义。实际操作就是将待调整的数沿着它的父节点和兄弟节点，一路向上或向下调整，使得整个数组最终符合堆的定义。复杂度是O(logN)。

堆的构建

以构建最大堆举例，给定一数组，从倒数第二层的最后一个非叶子节点开始（即最后一个有子节点的父节点开始）至根节点，对每个节点进行堆化，构建父节点大于子节点的结构。复杂度是O(N)。

S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1)

h是堆的高度，h=logN，比较的次数等于每层节点个数乘以比较次数，在第h-1层的节点向下比较1次，…，根节点比较h-1次。

公式两边乘2，得到2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1)，相减得到S =2^h × 1 - h + 1，将h=logN代入，最终得到S = n - logN +1 = O(N)

堆的删除节点

按定义，堆中每次都只能删除第1个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

堆的添加节点

将数添到数组的最后向上比较进行堆化，复杂度是O(N)。

堆排序

以升序（降序）为例，先对数组构建最大（最小）堆，复杂度是O(N);然后从数组最后开始遍历，与数组顶部的节点进行交换，然后对顶部的元素进行堆化，这样可以保证数组最后的那些数是升序。最终得到排序的数组，复杂度是O(NlogN)。

堆的几个应用

堆的几个应用
堆排序及其应用

另外Dijkstra算法中每次找离源点最近的一个顶点也可以用堆来优化，使算法的时间复杂度降到O((M+N)logN)。堆还经常被用来求一个数列中第K大的数。只需要建立一个大小为K的最小堆，堆顶就是第K大的数。如果求一个数列中第K小的数，只最需要建立一个大小为K的最大堆，堆顶就是第K小的数，这种方法的时间复杂度是O(NlogK)。当然你也可以用堆来求前K大的数和前K小的数。你还能想出更快的算法吗？有兴趣的同学可以去阅读《编程之美》第二章第五节。

堆排序算法是由J.W.J. Williams在1964年发明，他同时描述了如何使用堆来实现一个优先队列。同年，由Robert W．Floyd提出了建立堆的线性时间算法。

参考资料：

堆 上
堆 下
堆和优先队列
堆排序及其应用