图解堆排序（一）什么是堆及其性质

1. 引言

在上一篇文章中，我们了解到堆排序面临两个主要问题：

1、将一个序列构造成一个大顶堆；

2、取出大顶堆的根节点后，调整其剩余节点，使它们形成新的大顶堆。

第一个问题也可以通过第二个问题的解决来解决，所以我们先解释第二个问题。

2. 堆调整

2.1 算法概述

删除堆的根节点后，调整其剩余节点以使其重新形成堆的过程称为堆调整。这里以大顶堆为例介绍堆调整过程，小顶堆调整过程类似。

取出大顶堆的根节点后，将大顶堆的最后一个节点移动到根节点的位置作为新的根节点，如图1所示。此时，这个新的完全二叉树仍然是大顶堆，但是新的根节点可能不满足大顶堆的要求。这也是大顶堆调整的前提条件，即完全二叉树的左右子树都是大顶堆，只有根节点可能不满足大顶堆的要求。

假设此时新的根节点满足大顶堆的要求，即它的值大于等于它的左右子节点的值，那么这棵新的完全二叉树已经是一棵了顶堆大，调整完成。

但在图1中，新的根节点的值为39，比它的左右子节点小，不满足大顶堆的要求（这种情况在图中用红色表示）。因此，根节点仍然需要调整。

图1 让最后一个节点成为新的根节点

选择根节点中较大的子节点，与较大的子节点交换位置，如图2所示。交换后的新根节点一定是所有节点中最大的，因此大于或等于其左边和正确的孩子。以未交换子节点为根的子树不受影响，它仍然是一个大顶堆；而另一个子树（现在以原始根节点为根）可能不再是一个大顶堆。

在图2 中，根节点（值39）及其右子节点（值83）被交换，新的根节点（值83）大于或等于其左子节点和右子节点。左子树（以值77 为根）不受影响，并且仍然是一个大的顶堆。右子树（现在以值39 为根）不再是一个大的顶堆，因为值39 小于其左子树的值。

图2 大顶叠调整流程1

右子树原来是一个大顶堆，但是它的根节点被交换了，所以它的左右子树仍然是一个大顶堆，只是现在它的新根节点不满足大顶堆的要求。因此，现在这棵子树也满足了顶堆大调整的前提，我们需要再次调整该子树的新根节点。该子树的调整过程与之前的调整类似，如图3所示。

图3 大顶叠调整流程2

在图3 中，子树的根节点（值39）的较大子节点是其左子节点（值61），因此这两个节点被交换。交换后，值为39的节点形成一棵只有一个节点的完全二叉树，即没有左右孩子，因此满足大顶堆的要求。至此，整个完整的二次树也就成为了一个大顶堆，所以调整过程就结束了。

2.2 算法实现

我们用C语言实现大顶堆调整算法。实现代码直接对应了我们上面的算法讲解，并且代码中给出了非常详细的注释，所以代码应该很容易理解。

这个实现中需要注意的一点是，当我们交换父节点和其较大的子节点时，我们只将子节点的值写入父节点的位置，而不写入父节点的值。到子节点，这就是为什么下面代码的第56 行被注释掉的原因。

这是因为父节点经过一次调整后，可能会继续调整多次，这样它刚刚交换到的位置就会立即被它的新子节点（较大的那个）覆盖。因此，只需要将父节点写入到最后时刻最终调整的位置即可，这样可以减少一些消耗；下面代码的第61行就是用来实现这个目的的。

/** * Function: heapAdjust * 描述： 大顶堆调整算法的实现* param: 数组该序列存储要调整为大顶堆的完全二叉树* param: start 完全二叉树根节点在中的下标sequence * param: end 序列中完全二叉树最后一个节点的下标*/void heapAdjust(int array[], int start, int end) { /* *parent 表示要调整的节点的下标， * child 是父节点的下标， * temp 用于交换节点的值。 */int 父级； int 孩子；国际温度； /** * 初始化parent为start，因为一开始，*要调整的节点是完全二叉树的根节点，根节点的下标是start； * 将temp设置为根节点的值。 */父=开始；临时=数组[开始]； /** * 首先将child设置为父节点左子节点的下标， * 父节点左子节点的下标为2*parent+1 ; */for(child=2 * Parent + 1; child=end; child=2 * Parent + 1) { /** * 如果child小于end，则父节点也有右孩子，且下标为右孩子*是孩子+1；如果左孩子小于右孩子，则增加*child的值，使其成为右孩子的下标。 */if(child end array[child] array[child+1]) { ++child; } /** * 此时child就是父节点较大child的下标； * 如果temp（是父节点的值）大于等于子节点的值， * 则父节点已经满足大顶堆的要求，调整完成， * 退出循环此时。 */if(temp=array[child]) { 中断； } /** * 否则，父节点的值小于子节点的值，需要交换； * 交换后，将parent设置为child，因为父节点的点已经下移*到了其子节点的位置。 */数组[父]=数组[子]; //数组[子]=临时；父=子； } //如果调整到的父节点的最终位置不是其起始位置，则写入if(parent !=start) { array[parent]=temp; }}

3. 堆构造

3.1 算法概述

要将序列构造为堆，我们只需在序列对应的完全二叉树中从下到上、从右到左按顺序对每个子树应用堆调整算法即可反复。从原序列的最后一个元素开始，向前遍历每个元素，每遍历一个元素，就会在一大堆中调整以该元素为根节点的子树。因为是从后向前遍历，所以每遍历一个元素，它的左右子树就已经是大堆了。因此，以元素为根的完全二叉树可以直接使用大堆调整算法。对根节点（序列中的第一个元素）应用大堆调整后，原始序列被构造成一个大堆。

因为叶子节点没有子节点，所以以叶子节点为根的子树本身就是一个很大的顶堆，所以我们可以从最后一个内部节点开始向前遍历。最后一个内部结点一定是最后一个结点的父结点（其下标为n-1），所以最后一个内部结点的下标为(n-1-1)/2。

我们还是用一个例子来展示大顶堆构建的完整过程，假设原始序列为[35,52,61,39,29,96,83,43,77]。我们首先将序列表示为一棵完全二叉树，因为该树共有9 个节点，所以最后一个内部节点的索引为3。我们对以节点号3 为根的子树进行大的顶堆调整，如下所示图4.图中的虚线框表示我们正在调整的子树。

图4 对编号3的节点进行栈顶大调整

然后对以编号为2的节点为根的子树进行顶堆大调整，如图5所示。

图5 对编号2的节点进行栈顶大调整

然后对以编号1节点为根的子树进行顶堆大调整，如图6所示。

图6 对编号1的节点进行栈顶大调整

最后，将大顶堆调整为以编号为0的节点为根的子树（实际上是整个完整二叉树），如图7所示。至此，整个序列就构造成了一个大顶堆。

图7 对编号为0的节点进行顶堆大调整

3.2 算法实现

我们还用C语言实现了构造大堆的算法。实现代码还是直接对应了我们上面的算法讲解，并且代码中给出了非常详细的注释。因为堆的构建是基于堆调整的，所以这里需要调用第2节中实现的heapAdjust()函数。

这段实现代码中有一点需要注意。我们在第2节实现heapAdjust()函数时说过，它的第三个参数end是要调整的完全二叉树的末尾（代表要调整的一个大顶堆）。序列中节点的索引。那么当我们调整不同的子树时，传递给heapAdjust()函数的第三个参数应该是序列中子树最后一个节点的下标。