图解堆排序（一）什么是堆和堆的性质
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行代码的作用正是为了实现这一目的。
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()函数的第三个参数应该是该子树的最后一个结点在序列中的下标。
但是看下面代码中的第20行，我们每次调用heapAdjust()函数时传递的第三个参数都是n-1，它其实是整个序列中最后一个元素的下标。之所以这样做，是基于以下两点原因：
1. 每次都要计算当前子树的最后一个结点的下标比较麻烦，而且需要额外的开销；
2. 将最后一个参数统一设置为n-1在所有子树中都没有引入多余的结点，此时该子树的结构是不变的，因此调整结果是正确的。假设这一操作为某个子树引入了一个多余的结点，那么该结点之前也必定不存在于整棵树（代表整个序列）中，那么引入后它的下标应该大于n-1；但我们实际已知所有结点的下标都小于等于n-1，所以假设不成立。
（完）
热门跟贴