现在来看， 堆的含义大概有两种，一种是数据结构，一种是在一些语言中所定义的“垃圾回收机制”，如Java，在书本上的开篇强调了这两者，并强调若非特殊说明，皆把堆看做是一种数据结构。
（二叉）堆的定义：
1）它是一个数组，可以被看成是一棵近似的完全二叉树，树上的每一个节点看做是数组中的每一个元素。
2）堆分为最大堆和最小堆，最大堆中每一棵子树的父节点的值大于孩子节点，最小堆则相反。
3）表示堆的数组A包括两个属性：A.length和A.heap_size。前者是数组元素的个数，后者是堆元素的个数，heap_size <= length。（怎么理解这里，想象一棵树的节点在减少，但其表示的数组的个数还是不变的）。
4）二叉堆是最常用的，除此之外，还有多叉堆，如习题6-2的d-叉堆。
5）已知一个节点的坐标，容易得到其父节点和孩子节点的坐标：PARENT(i) = i/2; LEFT(i) = 2*i; RIGHT(i)=2*i+1。
由于二叉堆可以看做是一棵完全二叉树，所以树的一些定理，结论可以应用到堆上，如高度为h的堆中元素个数最多为：2^h，最少为：2^(h+1) - 1; 含n个元素的堆高度为：lgn。
堆排序：
为了实现堆排序，需要有这样的几个过程：
1）Build_Max_Heap():建立最大堆，将无序的输入数组构造出一个最大堆；
2）Max_Heapify():维护一个最大堆，即保证满足最大堆的性质；
3）Heap_Sort():堆排序。
以上函数的思路也是比较简单，在此就不做过多记录，即便记录，也是照着书本上的流程来一遍。
首先，Max_Heapify()是一个很关键的函数，它要保证堆中元素在以后的操作过程中，不管怎么变，都要保证满足最大堆的性质，即父节点的值永远大于孩子节点，知道了这一点，就不难写出代码：
函数原型：Max_Heapify( int A[], /* int heap_size, */ int index )
View Code
上面实现的是一个递归的版本，也是书本上的版本，同时习题6.2-5要求实现非递归的版本，其实改动很小，只需加入一个标识符即可，实现如下：
其次，Build_Max_Heap()的实现需要知道下面一条定理( 习题6.1-7 ) :
当用数组表示存储n个元素的堆时，叶节点下标分别是n/2+1, n/2+2, ..., n (结合树高度的性质，很好证明).
知道了这个定理，为了建立最大堆，我们就可以从第一个非叶子节点开始往后遍历，直到根节点，调用Max_Heapify()来得到一个最大堆，实现如下：
函数原型：Build_Max_Heap( int A[], /* int heap_size, */ )
至此，排序思路也就出来了：先建立最大堆，得到最大元素，然后将最大元素放在数组末尾，然后调用Max_Heapify()维护最大堆，依次下去，就得到排序的数组，实现如下：
函数原型：Heap_Sort( int A[], /* int heap_size, */ )
堆排序的时间复杂度：
Max_Heapify()可以看到是在不断遍历树，最坏情况下是从根节点开始，则n个节点的树高为lgn，所以其时间复杂度为O(lgn)。
Build_Max_Heap()经过严格推导，可得时间复杂度为线性的，为O(n)。
所以，Heap_Sort()就为O(nlgn)。
同样的思路可以实现最小堆，下面贴出最大堆完整实现的代码：