堆是一个重要的数据结构，（二叉）堆数据结构是一种数组对象，可以看成一棵完全二叉树，没个结点与数组中的存放位置对应。
表示堆的数组有两个属性：length[A]，heap_size[A],前者是数组A中元素个数，后者指相应堆中的有效元素，所以heap_size[A]<=length[A]。给定某结点的下标，可以得出其父结点parent(i),左孩子left(i),右孩子right(i)。
parent(i) return i/2（下取整） left(i) return 2i right(i) return 2i+1
二叉堆有两种：1.最大堆 2.最小堆
最大堆性质：除根结点外，A[parent(i)] >= A
最小堆性质：除根结点外，A[parent(i)] <= A
堆排序算法：应用最大堆，是一种效率为O(nlgn)的原地排序算法。
保持堆性质 max_heapfy 对最大堆进行操作的子程序，输入为一个数组A和下标i，调用函数时，假定以left(i)和right(i)为根的两棵子树都为最大堆，但是A可能小于其子女，max_heapfy让A在最大堆中“下降”，使i为根的子树成为最大堆。
max_heapfy(A,i)----------------O(lgn)或者O(h) h = lgn
建堆，自底向上调用max_heapfy将一个数组A[1..n]变成一个最大堆。因为在堆中A[(n/2+1)..n]（n/2下取整）中的元素为树中的叶子，所以过程build_max_heap中迭代由n/2 down to 1
bulid_max_heap(A)--------------O(n)
排序，首先调用bulid_max_heap建堆，此时，最大元素为A[1]，所以在i次迭代中（i由n down to 2），将A[1]与A交换，更新heap_size[A],再调用max_heapfy(A,1)对最大堆维持。
heap_sort(A)--------------------O(nlgn)
优先级队列：应用最大堆、最小堆性质，维持一组元素集合的数据结构
insert(A,key):将key插入A[heap_size[A]+1],再“上升”
delete_max(A):returnA[1],再将A[1] <- A[heap_size[A]],调用max_heapfy(A,1)维持
由此，所有在优先级队列上的操做，均可以在O(lgn)的时间内完成。
这里只列举了最大堆，最小堆与其类似。
其他应用，排序链表的k路合并：将k个排序的链表合并为一个排序链表,应用最小堆，可以设计一个时间为O(nlgk)的算法，其中n为总的元素个数。