堆排序

输入：n个数的一个序列 (A[1..n])

输出：输入序列的一个排序，满足b1≤b2≤…≤bn。

堆

表示堆的数组A包括两个属性：A.length给出数组元素的个数，A.heap-size表示有多少个堆元素存储在该数组中。也就是说，虽然A[1..A.length]可能都存有数据，但只有A[1..A.heap-size]中存放的是堆的有效元素。这里, 0 ≤ A.heap-size ≤ A.length。

（二叉）堆数组A是一个近似的完全二叉树，树的根结点是A[1]，这样，给定一个结点的下标i，它的父节点、左孩子和右孩子的下标：

`PARENT(i): return i/2// i>>1

LEFT(i): return2i// i<<1

RIGHT(i): return2i+1// i<<1 + 1

`

最大堆：堆的最大元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。即：A[PARENT(i) ≥ A[i]。堆排序使用最大堆。

最小堆：堆的最小元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不小于该子树根结点的值。即：A[PARENT(i) ≤ A[i]。最小堆常用来构造优先队列。

堆中结点的高度：该结点到叶结点最长简单路径上边的数目。

堆的高度：根结点的高度。O(lgn)。其中，n为堆中元素个数。