首页 > 代码库 > 算法学习之排序算法：堆排序
算法学习之排序算法：堆排序
要了解堆排序，首先要了解堆的概念，因为本文主要研究堆排序的算法，此处对数据结构堆只是给出概念：n个元素的序列{k1,k2,...kn}，当且仅当满足如下关系时，称之为堆。
k[i] <= k[2i]且k[i] <= k[2i+1] （或k[i] >= k[2i]且k[i] >= k[2i+1]）
比如：序列96、83、27、38、11、09（或12、36、24、85、47、30、53、91）都是堆。
如果将堆对应的一维数组看成是一个二叉树，则堆的含义表明：完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。将上面的一维数组形式的堆改写成二叉树形式的堆如下：
96 12
/ \ / \
83 27 36 24
/ \ / / \ / \
38 11 9 85 47 30 53
/
91
由上面给出的一维数组的堆和二叉树堆例子可以看出，若序列{k1,k2,...kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
堆排序的过程：若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又简称一个堆，则得到n个元素中的次小值。依次反复执行，使能得到一个有序序列。
实现堆排序需要解决两个问题：
1、由一个无序序列建成一个堆。
2、在输出堆顶元素之后，调整剩余元素成为一个新的堆。
下面以序列{49、38、65、97、76、13、27、49}为例，分析如何进行建初始堆以及输出堆顶元素后如何调整建新堆。
从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第[n/2]个元素，由此“筛选”只需从第[n/2]个元素开始。以构造“最小值堆”为例：
49
/ \ 图a：因为n/2向下取整是4，第4个元素的值是97，
38 65 在最小值堆中非终端结点的值应该小于它
/ \ / \ 的左右孩子的值，此处97>49，因此将97与49交换。
97 76 13 27 得到图b。
/
49
（a）
49
/ \ 图b：按照顺序筛选第3个元素65，
38 65 因为65>13，所以将65与13交换，得到图c。
/ \ / \
49 76 13 27
/
97
（b）
49
/ \ 图c：按照顺序筛选第2个元素38，
38 13 因为38不大于其左右孩子，则筛选序列不变，得到图d。
/ \ / \
49 76 65 27
/
97
（c）
49
/ \ 图d：按照顺序筛选第1个元素49，
38 13 因为49>13，所以交换之，
/ \ / \ 又因为交换后的元素49仍然大于27，
49 76 65 27 继续与27进行交换，得到图e，即为构造的堆。
/
97
（d）
13
/ \ 图e：构造的堆。
38 27
/ \ / \
49 76 65 49
/
97
（e）
13
/ \ 图a：取出构造的堆顶元素13作为排序后
38 27 有序序列的第一个元素：{13}。
/ \ / \ 输出堆顶元素13之后，以堆中最后一个元素97替代之。
49 76 65 49 得到图b。
/
97
(a）
97
/ \ 图b：将97置于根结点之后，它的左右子树（图中的绿色与红色标记）
38 27 仍然为堆。仅需要自上之下调整，使整个数为堆即可。首先以堆
/ \ / \ 顶元素和其左右子树根结点的值比较，由于右子树根结点的值
49 76 65 49 小于左子树根结点的值且小于根结点的值，则将27和97交换之。
得到图c。
13
(b)27
/ \ 图c：由于97替代了27之后破坏了右子树的“堆”，则需要进行和上述
38 97 相同的调整，直至叶子结点，得到图d。
/ \ / \
49 76 65 49
13
(c)27
/ \ 图d：此时的二叉树是一个堆，堆顶为n-1个元素中的最小值。取出
38 49 该n-1个元素中的最小值（n个元素中的次小值）。
/ \ / \ 重复前面的步骤，依次得到最小的值。从而完成堆排序。
49 76 65 97
13 27
(d)注意：堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。堆排序在最坏的情况下，其 时间复杂度为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交 换用的辅助存储空间。
算法学习之排序算法：堆排序