Part_1：堆基础介绍
堆（二叉堆）是一个数组，近似的二叉树，通常采用数组来构建：A[1...A.length],数组中并不一定全是堆得有效数据，可以只有A.heap_size个有效的堆元素。
当给定一个节点的下标 i，可知其父节点、左孩子、右孩子的下标：
Parent(i) return floor(i/2) Left(i) return 2i Right(i) return 2i+1
二叉堆有最大堆（A[Parent(i)]>= A[i]）和最小堆(A[Parent(i)] <=A[i])，堆排序算法中使用的是最大堆；而最小堆常用于构造优先队列。
如前所述，堆其实就是一棵树，那么树中节点的高度就是该节点到叶节点最长简单路径上边的数目，而堆得高度就是根节点的高度。一个包含n个元素的堆，其高度就是Θ(lgn)。
堆的高度很重要，因为堆结构上的一些基本的运行时间与高度有很大关系。
Part_2 : 堆性质维护（以最大堆为例）
最大堆性质的维护是一个很重要的过程。假设 i 的左右子树均为最大堆，A[i]可能小于其左右子树的根节点的值，那么如何通过调整节点的"阶层"来维护最大堆呢？下面看一下MAX-HEAPIFY(A,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],A[largest]) MAX-HEAPIFY(A,largest)
对于一个树高位h的节点来说，MAX-HEAPIFY的时间复杂度为O(h)。
Part_3 : 建堆
堆性质的维护是通过“逐级下降”的方式，而堆得建立是通过“自底向上”的方式。子数组A[floor(n/2)+1 ... n]是树的叶节点。BUILD-MAX-HEAP对树中的其它节点调用一次MAX-HEAPIFY。
BUILD-MAX-HEAP(A)：
A.heap_size = A.length for i=floor(A.length/2) to 1 MAX-HEAPIFY(A,i)
Part_4 : 堆排序
堆排序：首先，将输入数组建成最大堆；其次，将堆中最大元素A[1]与A[n]位置互换，这样新的根节点可能不满足最大堆的性质；最后，通过调用MAX-HEAPIFY在A[1 ... n-1]上构造新的最大堆，重复该过程，直到堆得大小变为2。HEAPSORT(A):
BUILD-MAX-HEAP(A) for i =A.length to 2 exchange(A[1],A[i]) A.heap-size -- MAX-HEAPIFY(A,1)