数据结构之堆

一、堆

堆是一种数据结构，通常通常所说的堆即二叉堆。二叉堆是一个数组，可以被看成一个完全二叉树，如下图所示：

他在数组中的表现形式为：

通过数组很容易得到每个父节点和其子节点的关系，假设数组的起始下标为 0，那么有：

因此可以直接在程序中定义：

二、最大堆和最小堆

堆有最大堆和最小堆之分，在最大堆中，除了根节点以外的所有节点 i 都要满足：A[PARENT[i]] >= A[i]，所有的子节点的值不会超过其父节点的值。因此，在最大堆中，最大的元素存放在根节点中。

而最小堆和最大堆相反，除了根节点以外的所有节点 i 都要满足：A[PARENT[i]] <= A[i]， 所有子节点的值都大于等于其根节点的值。因此，最小堆中根节点的元素是最小的。

在堆排序算法中，使用的是最大堆，最小堆通常用于构造优先级队列。

以最大堆为例，其包含的操作为：

• MAX_HEAPIFY：用来维护一个最大堆。
• BUILD_MAX_HEAP：从一堆无序的数组中构造出一个最大堆。
• HEAPSORT：执行一次堆排序过程。

三、最大堆

3.1 维护最大堆

把一个堆构造成最大堆的流程：

1. 从 A[i], A[LEFT[i]], A[RIGHT[i]] 中选出最小的，保存其下标 largest 。
2. 如果 largest 不等于 i，交换 A[i] 和 A[largest] 。

以下图为例，当前堆中 4 处于一个非正确的位置：

首先把 4 和其儿子中最大的 14 交换，得到以下堆：

交换后 4 依旧不是最小的元素，继续交换 4 和 8：

4 当前已经是叶子节点了，此时对 4 的最大堆化操作就完成了。并且此时的堆也就是一个最大堆。

不难看出：对一个高度为 h 的树来说，这个操作的时间复杂度为 O(h)。

对应的 c 代码：

3.2 建堆

建堆的过程实际上是执行多次 MAX_HEAPIFY，我们只需对 2/n 以内的元素都执行 MAX_HEAPIFY 操作即可完成一个最大堆的构建。

因为 [n/2, n) 之间的元素都是叶子节点，所以无需对它们进行转换操作。

要注意的是建堆必须从下往上，否则可能出现堆只是局部有效，对全局而言并非有效：

以上图为例，如果从上到下建堆，在调整完 4 的位置之后，14 被放在了树根。而实际上被放在树根的应该是 16，因为接下来就不会调整 14 了，它的位置就永远不对，这个堆也就不是一个符合要求的堆。

代码：

四、堆排序

参考：排序算法之堆排序