3. 堆排序
已经介绍过了两种相对简单的排序算法（插入排序、合并排序）之后，我们将介绍一种稍微难一些的排序算法——堆排序（heapsort）。
堆排序在运行时间上与合并排序相似，同时又是一种原地(in place)排序算法（在任何时候，数组中只有常数个元素存储在输入数组以外），结合了插入排序和合并排序两种排序算法的优点。
3.1 堆
（二叉）堆数据结构是一种数组对象，它可以被视为一棵完全二叉树。数中每个节点与数组中存放该节点值的那个元素对应（如图3-1,3-2所示）。
一个最大堆可以看作一棵二叉树（如图3-1所示），也可以看作一个数组（如图3-2所示）。
二叉树中：
圆圈中的数字表示数中每个节点存储的值，节点上方的数字表示对应的数组下标。
数组中：
数组上下的连线表示父子关系，且父节点总是在子节点的左边。
这里需要简单的补充一些知识：
最大堆，堆中的最大元素存放在根节点中，并且，在以某一个节点为根的字数中，各节点的值都不大于该子树根节点的值。图3-1所示的二叉树就可以称之为最大堆。
3.2 建堆
建堆是指将“原数组所等价的堆”转换为“最大堆”的过程。
从最后一个子树（即从以标号为i/2的节点为父节点的子树）开始，自底向上地建立最大堆。以原数组为{4,1,3,2,16,9,10,14,8,7}为例，其具体过程如图3-3所示。
过程详细解释如下（若了解过程，可跳过此段）：
A）：一个包含10个元素的数组，将其表示为堆的形式。从父节点标号为5（10/2=5）的子树开始，自底向上构建最大堆。由于16>7，故此时该子树符合最大堆性质，故不做修改。然后，将目标父节点标号减一变为4，即对父节点标号为4的子树构建最大堆。
B）：对于父节点标号为4的子树，由于14>8>2，故将节点标号为4（其值为2）与节点标号为8（其值为14）的值互换。值互换之后，父节点标号为4的子树符合最大堆性质，故此子树的最大堆构建完成。然后，将目标父节点标号减一变为3，即对父节点标号为3的子树构建最大堆。
C）：对于父节点标号为3的子树，由于10>9>3，故将节点标号为3（其值为3）与节点标号为7（其值为10）的值互换。值互换之后，父节点标号为3的子树符合最大堆性质，故此子树的最大堆构建完成。然后，将目标父节点标号减一变为2，即对父节点标号为3的子树构建最大堆。
D）：对于父节点标号为2的子树，由于16>14>1，故将节点标号为2（其值为1）与节点标号为5（其值为16）的值互换。与之前不同的是，此时值互换之后，父节点标号为2的子树并不满足最大堆性质，故将目标父节点变换至标号为5的节点。由于7>1，故将节点标号为5（其值为1）与节点标号为10（其值为7）的值互换。值互换之后，父节点标号为2的子树满足最大堆性质。故继续如C中所示，将目标父节点变为1，即对父节点标号为1的子树（即整个二叉树）构建最大堆。
E）：对于父节点标号为1的子树，由10>4>1，故将节点标号为1（其值为4）与节点标号为2（其值为16）的值互换。与D中相同，值互换之后，父节点标号为1的子树并不满足最大堆性质，故将目标父节点变化至标号为2的节点。由于14>7>4，故将节点标号为2（其值为4）与节点标号为4（其值为14）的值互换。值互换之后，父节点标号为1的子树仍然不满足最大堆特征，故将目标父节点变换至标号为4的节点。由于8>4>2，故将节点标号为4（其值为4）与节点标号为9（其值为8）的值互换。值互换之后，父节点标号为1的子树（即整个二叉树）满足最大堆性质。
至此，建立最大堆的过程完成。
3.3 堆排序
对于数组A[1]……A[n]，通过构建最大堆可知，数组中最大的元素在A[1]，则可以通过把A[1]与A[n]互换，使该数字达到最终正确的位置。现在，如果从堆中“去掉”节点n，则可以较容易地构建数组A[1]……A[n-1]的最大堆（即只需要重新构建目标父节点标号为1的子树）。此后不断重复这一过程，直至堆的大小降为1，此时，即完成了最终的排序过程。其具体过程如图3-6所示。
以a)到b)的转换过程为例，对该过程进行细部详解，如图3-7所示。
C代码实现如下：
C++代码实现：