堆排序法

堆排序（Heap Sort）也是一种选择排序算法，它利用堆结构和二叉树的一些性质来完成数据的排序。

算法描述 

在介绍堆排序之前，首先了解什么是堆。 

堆是一个完全二叉树，树中每个节点对应于原始数据的一个记录，并且每个节点应满足以下条件： 

（1）如果按照从小到大的顺序排序，要求非叶节点的数据要大于或等于其左、右子节点的数据。 

（2）如果按照从大到小的顺序排序，要求非叶节点的数据要小于或等于其左、右子节点的数据。

提示 在堆中，对节点的左孩子和右孩子的大小没有要求，只规定父节点和子节点数据之间必须满足的条件。当要按从小到大的顺序输出数据时，要求根节点为最大值。

下面以按从小到大的顺序排序为例，介绍堆排序的相关内容。 由堆的定义可看出，其根节点为最大值，堆排序就是利用这一特点进行排序的。

堆排序过程包括以下两个阶段： 

（1）将无序的数据构成堆（即用无序数据生成满足堆定义的完全二叉树）。 

（2）利用堆排序（即将上一步生成的堆输出，得到排序后的有序数据）。

1．构成堆 

构成堆就是把无序的数据按堆的定义进行交换调整，使父节点的数据大于子节点的数据。构成堆的具体步骤如下。 

（1）将无序数据放入完全二叉树的各节点。 

（2）由二叉树的下层向上层逐层进行父子节点的数据比较，使父节点的数据大于子节点的数据，可以使用一种称为“筛”的运算进行节点数据的调整，直到使节点最后满足堆的 条件为止。

筛运算针对非叶节点进行，以非叶节点Ai 的筛过程为例，当对Ai 进行筛运算时，比它编号大的非叶节点都已进行过筛运算，即已形成了以各非叶节点为根的堆，其中包括以Ai 的左、右孩子为根的堆（若A2i 和A2i+1 为叶节点，则认为叶节点是堆）。所以，对Ai 进行筛运算是在其左、右子树均为堆的基础上实现的。具体过程为：

（1）确定Ai 的两个子树的最大值，放在Aj中。

（2）将Ai 的数据与Aj 的数据进行比较，如果Ai ≥Aj ，表示以Ai 为根的子树已构成堆，筛运算完成。

（3）若Ai <Aj ，则将Ai 与Aj 互换位置，互换位置后可能会破坏以Ai （此时Ai 的值为原来的Aj ）为根的堆，接着再以Aj 为根重复前面的步骤，直到父节点数据大于子节点，或子节点为空时为止。这样，以Aj 为根的子树就被调整为一个堆。

提示 在以上过程中，在对Aj进行的筛运算中，若其值较小，则会被逐层下移。这样，较小的数据就像被筛子筛下去，而较大的数据保留在筛子上面，所以把构成堆的过程形象地称为筛运算。

下面以一组待排序的数据演示构成堆的过程，假设有8个需要排序的数据序列如下：

 69，65，90，37，92，6，28，54 

下图给出构成堆的全过程，下图中a为无序数据构成的完全二叉树，具体过程如下：

（1）首先对最后一个非叶节点（节点4）进行筛运算，使其与子节点进行比较，因该子节点只有左子树（节点8），而37<54，需对这两个节点位置进行互换，得到图b。此 时，节点4及其子节点构成堆。

（2）接着对二叉树中倒数第2个非叶节点（节点3）进行筛运算，因节点3的两个子节点中节点7的值较大，因此使节点3与节点7进行比较，90>28，不需要进行互换，得到图c。此时，节点3及其子节点构成堆。 

（3）对二叉树中倒数第3个非叶节点（节点2）进行筛运算，因节点2的两个子节点中节点5的值较大，因此使节点2与节点5进行比较，65<92，将节点2与节点5的数据进行互 换，得到图d。此时，节点2及其子节点构成堆。 

（4）对二叉树中倒数第4个非叶节点（节点1）进行筛运算，因节点1的两个子节点中节点2的值较大，因此使节点1与节点2进行比较，69<92，将节点1与节点2的数据进行互 换，得到图e。此时，因节点2的值已改变，可能破坏了节点2与其子节点构成的堆，需要重新对节点2及其子节点进行运算。在本例中，节点2比两个子节点的值都大，符合堆的 要求。此时，节点1及其子节点构成堆。至此，就将完全二叉树构成了一个满足要求的堆。

2．利用堆排序

使用上面的步骤构成堆以后，接下来的工作就是通过堆输出有序的数据。 从图e生成的堆可看出，节点1的值是整个二叉树中最大的，按顺序输出时，需将其放在数组的最后。根据这个规律，将堆按顺序输出数据的过程如下：

（1）取堆的根节点（最大值），将其放到数组的最后。由于数组元素的最后一个元素保存着节点8的值37，因此，将节点8的值与节点1互换。 

（2）节点8的值37换到根节点后，重新执行前面介绍的构成堆的方法，此时，应将最后一个节点排除在外。 

（3）重复上面的过程，逐步从根节点取出最大值，放入数组的后面，再对剩下的节点重新构造成堆，直到只剩下一个节点，即可得到有序的数据。

根据以上描述过程，将上图e所示的堆进行排序，如下图所示。具体过程如下： 

（1）从图4-11a的根节点选择，将其与最后一个节点8交换，得到图4-11b。 

（2）根据图4-11b重新构成堆，得到c图。 

（3）重复上面的步骤，将根节点与最后一个节点（节点7）交换，得到图4-11d，再将剩下的节点重新构成堆。就这样不断重复，最后可得到排序后的数据。