1、堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如最小堆示例和最大堆示例所示。
堆排序算法
2、最大堆和最小堆
（1）根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为最小堆。
（2）结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为最大堆。
注意：
（1）堆中任一子树亦是堆。
（2）以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
3、堆排序的基本思路如下:
（1）把待排序数组构造成一个最大堆
（2）取出树的根(最大(小)值, 实际算法的实现并不是真正的取出)
（3）将树中剩下的元素再构造成一个最大堆(这里的构造和第1步不一样，具体看实现部分)
（4）重复2,3操作，直到取完所有的元素
（5）把元素按取出的顺序排列，即得到一个有序数组(在代码实现里是通过交换操作"无形中"完成的)
在开始实现算法先看几个结论(证明略):
（1）完全二叉树A[0:n-1]中的任意节点，其下标为 ii, 那么其子节点的下标分别是为2i+12i+1 和 2(i+1)2(i+1)
（2）大小为n的完全二叉树A[0:n-1]，叶子节点中下标最小的是⌊n2⌋⌊n2⌋， 非叶子节点中下标最大的是⌊n2⌋−1⌊n2⌋−1
（3）如果数组是一个最大堆，那么最大元素就是A[0]
（4）最大堆中任意节点的左右子树也是最大堆
4、实现示例
