算法 | 堆排序（heap sort)

   
注：本文只讨论最大堆排序，最小堆排序同理



一 . 堆
 
堆（heap）可以定义为一棵完全二叉树，并且这棵树的每一个节点都大于或等于它的子女节点。

 最大堆长这样子：

堆的特性

1. 一棵n节点的完全二叉树，其高度为$$\lfloor \log_{2}n\rfloor$$
2. 堆的每一个节点都大于等于它的子女节点。
3. 可以用数组来实现堆。留空H[0]，然后在H[1]到H[n]中存在堆元素。留空H[0]的目的是为了让之后的堆排序更加的方便。
4. 所有父母节点的键会在数组的前$$\lfloor n/2 \rfloor$$ 个位置中，而叶子节点会占据后面的$$\lceil n/2 \rceil$$个位置。
5. 在数组中，对于每一个位于父母位置i的键来说，它的子女会位于2i和2i+1
6. 对于一个位于位置i的键来说它的父母将会位于$$\lfloor i/2 \rfloor$$

如何生成堆

自底向上堆构造（bottom-up heap construction）：

对每个父母节点进行父母优势检查：

1. 从最后的父母节点开始，到根为止，检查这些节点的键是否满足父母优势要求。
2. 如果该节点不满足，就把该节点的键K与它子女的最大键进行交换。
3. 然后再检查新位置上，K是不是满足父母的优势要求。

效率：

最坏情况下，每个位于树第i层的节点都要移动到树的最底层h，因为移动一层需要两次键值比较，因此移动到h层需要 2(h-i) 次键值比较，所以总键值比较次数为：

自顶向下堆构造（top-down heap construction）：

把新的键连续插入到已经预先构造好的堆：

1. 把包含k附加到堆的最后一个叶节点的后面。
2. 拿k与它的父母节点作比较，如果k刚好小于它的父母节点，则算法停止。
3. 否则，交换k和其父母节点的位置
4. 重复2，3步骤直到k不大于它的父母，或者到达了根为止。

效率：
因为包含n个节点的树的高度大约是 log n ,因此每次插入的时间效率属于 O(log n)
总时间效率叠加即可。

二. 堆排序

堆排序的思路很简单：

1. 把数组构造成堆，此时根是最大值。
2. 把根从堆中“移除”，即把根节点和最后一个叶节点对换，然后把换到第一位的叶节点用堆排序安排至恰当的位置。
3. 重复2步骤直到堆中的元素全部 "删除" 完为止。

堆排序的完整代码：

三. 堆排序的效率

1. 第一阶段，用自底向上的方式进行堆构造，时间效率属于 O(n)
2. 第二阶段，每次消去根节点，又重新构造堆，最差情况下需要的键值比较次数记为 C(n). 有下面不等式：

$$C(n)\leq2\lfloor log_{2}(n-1)\rfloor+\lfloor log_{2}(n-2)\rfloor+……+\lfloor log_{2}1\rfloor
\leq 2\sum_{i=1}^{n-1}log_{2}i \leq 2\sum_{i=1}^{n-1}log_{2}(n-1) = 2(n-1)log_{2}(n-1) \leq 2nlog_{2}n$$

        因此第二阶段中C(n)属于 O(nlog n)
        因此总的时间效率为 O(nlog n)

实际上，堆排序的最差效率和平均效率都属于O(nlog n)，因此堆排序的时间效率和归并排序的时间效率属于同一类。
但是！堆排序是原地排序，不需要额外的存储空间，合并排序需要消耗至少一个数组的空间。