说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
堆排序是一种原地排序法，即在任何时候，数组中只有常数个元素存储在输入数组以外。由于该算法具有相当快的运行速度，且原地排序，所以结合了合并排序和插入排序的优点。
1、堆
（二叉） 堆 数据结构是一种数组对象(如下图所示)，它可以被视为一棵完全二叉树。树中每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层可能除外（最后一层从节点的左子树开始填）。
堆一般都用数组来表示，表示堆的数组 A 是一个具有两个属性的对象： A.length 是数组中元素的个数， A.heap-size 是存放在 A 中的堆元素个数。虽然A[1...A.length]都可以包含有效值，但A[A.heap-size]之后的元素都不属于相应的堆，所以有 A.heap-size <= A.length 。树的根为 A [ 1 ]，给定了某个结点的下标 i ，其父结点 PARENT(i) ，左儿子 LEFT(i) 和右儿子 RIGHT(i) 的下标可以简单的计算出来，公式如下（需要注意的是，在一个好的堆排序的实现中，这三个过程通常是用宏或者内联函数实现）：
PARENT(i) = FLOOR(i / 2)
LEFT(i) = 2i
RIGHT(i) = 2i + 1
最后一个非叶子节点下标为length[A]/2后向下取整
以上公式成立的前提是i从1开始到n。如果i从0开始到n-1，则公式如下：
PARENT(i) = FLOOR((i-1) / 2)
LEFT(i) = 2i + 1
RIGHT(i) = 2i + 2
二叉堆有两种： 最大堆 和 最小堆 (小根堆)。这两种堆都要满足各自的堆特性。在最大堆中，最大堆特性是指除了根以外的每个结点 i ，有 A [ PARENT(i) ] >= A [ i ]，即某个结点的值至多和其父结点一样大，这样，堆中的最大元素就存放在根结点中。最小堆的组织方式刚好相反，最小堆特性是指除了根以外的每个结点 i ，有 A [ PARENT(i) ] <= A [ i ]，最小堆的最小元素是在根部。
算法中使用何种堆：在堆排序算法中，我们使用的是最大堆。最小堆通常在构造优先队列时使用，具体将在书中6.5节，优先级队列中讲解。对于某个特定的应用，我们将确切的指明需要的是最大堆还是最小堆；当某一性质既适合最大堆，也适合最小堆时，我们就只使用堆这个词。
堆可以被看成是一棵树，结点在堆中的高度定义为从本结点到叶子的最长简单下降路径上边的数目；定义堆的高度为树根的高度。因为具有n元素的堆是基于一颗完全二叉树的，所以其高度为 Θ (lg n )。堆结构上的一些基本操作的运行时间至多与树的高度成正比，为 O (lg n )。下面将介绍几个基本过程，并说明它们在排序算法和优先级队列数据结构中如何使用：
1）、MAX-HEAPOFY 过程，运行时间为 O (lg n )，是保持最大堆性质的关键
2）、BUILD-MAX-HEAP 过程，以线性时间运行，可以在无序的输入数组上构造出最大堆
3）、HEAP-SORT 过程，运行时间为 O ( n lg n )，对一个数组进行原地排序
4）、MAX-HEAP-INSERT ， HEAP-EXTRACT-MAX ， HEAP-INCREASE-KEY ， HEAP-MAXIMUM 过程的运行时间为 O (lg n )，可以让堆结构作为优先级队列使用。
2、保持堆的性质，即MAX-HEAPOFY 过程==>是建堆的基本过程
MAX-HEAPIFY 过程的输入为一个数组 A 和下标 i 。当 MAX-HEAPIFY 被调用时，我们假定以 LEFT(i) 和 RIGHT(i) 为根的两棵二叉树都是最大堆，但这时 A [ i ]可能小于其子女，这样就违反了最大堆特性。 MAX-HEAPIFY 让 A [ i ]在最大堆中“下降”，使以 i 为根的子树成为最大堆。
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
largest = l
else
largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
下图描述了 MAX-HEAPIFY 的过程。在算法的每一步里，从元素 A [ i ]， A [ LEFT(i) ]和 A [ RIGHT(i) ]中找出最大的，并将其下标保存在 largest 中。如果 A [ i ]是最大的，则以 i 为根的子树已是最大堆，程序结束。否则，交换 A [ i ]和 A [ largest ]，从而使 i 及其子女满足堆性质。下标为 largest 的结点在交换后的值为 A [ i ]，以该结点为根的子树可能又违反了最大堆性质。因而要对该子树递归调用 MAX-HEAPIFY 。
当 MAX-HEAPIFY 作用在一棵以结点 i 为根的，大小为 n 的子树上时，其运行时间为调整元素 A [ i ]， A [ LEFT(i) ]和 A [ RIGHT(i) ]的关系时所用的时间 Θ (1)，加上对以 i 为结点的某个子结点为根的子树递归调用 MAX-HEAPIFY 所需的时间。 i 结点的子树大小至多为2 n / 3（最坏情况发生在最底层恰好半满的时候），那么 MAX-HEAPIFY 的运行时间可表示为： T ( n ) <= T (2 n / 3) + Θ (1)。该递归式的解为 T ( n ) = O (lg n )。或者说， MAX-HEAPIFY 作用于一个高度为 h 的结点所需的运行时间为 O ( h )，因为数的高度为lg n。
2、建堆，即BUILD-MAX-HEAP 过程
现在可以自底向上地用 MAX-HEAPIFY 来将一个数组 A [ 1 .. n ]（此处 n = A.length ）变成一个最大堆。因子数组 A [ FLOOR(n / 2) + 1 .. n ]中的元素都是树中的叶子结点，它们都可以看做是只含一个元素的堆，不用再通过MAX-HEAP过程降序来保证堆的性质，所以建堆的循环过程为 FLOOR(A.length / 2)--->1。过程 BUILD-MAX-HEAP 对树中的每一个非叶子结点都调用了一次 MAX-HEAPIFY来建堆 。总结来说建堆的过程就是i从到FLOOR(A.length / 2)到1逐步保持堆特性的过程，即从叶子节点的父节点一级逐级向上保持堆性质的过程！
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = FLOOR(A.length / 2) downto 1
MAX-HEAPIFY(A, i)
下图给出了 BUILD-MAX-HEAP 过程的一个例子。
我们可以计算出 BUILD-MAX-HEAP 运行时间的一个简单上界：每次调用 MAX-HEAPIFY 的时间为 O (lg n )，共有 O ( n )次调用，故运行时间是 O ( n lg n )。尽管这个界是对的，但从渐近意义上来说不够紧确。
实际上，我们可以得到一个更加紧确的界。因为，在树中不同高度的结点处运行 MAX-HEAPIFY 的时间不同，而大部分结点的高度都比较小。关于更紧确界的分析依赖于这样的性质：一个 n 元素堆的高度为FLOOR(lg n )，并且，在任意高度 h 上，至多有CEIL( n / 2( h + 1))个结点。
MAX-HEAPIFY 作用在高度为 h 的结点上的时间为 O ( h )，可以将 BUILD-MAX-HEAP 的代价表示为上确界：
最终可以得出 BUILD-MAX-HEAP 过程运行时间的界为
这说明可以在线性时间内，将一个无序数组建成一个最大堆。
