1.堆排序的定义
n个关键词序列Kl，K2，当且仅当序列满足以下属性(简称为堆属性)时，Kn称为堆：
(1) kiK2i和kiK2i 1或(2)KiK2i和kiK2i 1(1i)
如果向量R[1.n]存储在这个序列中被视为一个完整二叉树的存储结构，那么堆本质上就是一个完整的二叉树，具有以下性质：树中任意非叶节点的关键字不大于(或小于)其左右子节点(如果有的话)的关键字。
【示例】关键字序列(10、15、56、25、30、70)和(70、56、30、25、15、10)分别满足堆属性(1)和(2)，因此它们都是堆，它们对应的完全二叉树分别在hxsdgs堆和大根堆的示例中显示。
2.大根堆和hxsdgs堆
根节点(也称为堆的顶部)的键是堆中所有节点的最小键的堆称为hxsdgs堆。
根节点的关键字(也称为堆的顶部)是堆中所有节点中最大的关键字，称为大根堆。
注意：
堆中任何一个子树也是一堆。
上面讨论的堆实际上是一个二进制堆，同样可以定义一个K叉堆。
3.堆排序的特点
HeapSort是一种树选择排序。
堆排序的特点是：在排序过程中，将R [L.N]视为一个完整二叉树的顺序存储结构，利用完整二叉树中ngdkh节点与子节点的内部关系，在当前无序区域中选择关键字最大(或最小)的记录[参见二叉树的顺序存储结构]。
4.堆排序和直接插入排序的区别
在直接排序中，为了从R[1.n]，需要进行n-1次比较，然后从R[2]中选择关键字最小的记录.n]，并进行n-2次比较。事实上，在接下来的n-2比较中，许多比较可能是在之前的n-1比较中进行的。然而，因为这些比较结果没有保留在先前的排序中，所以这些比较操作在下一次排序中被重复。
堆排序可以通过树形结构保存一些比较结果，可以减少比较的次数。
5.堆栈排序
堆排序利用了大根堆(或hxsdgs堆)顶部记录的关键字最大(或最小)的特点，使得在当前无序区域中选择关键字最大(或最小)的记录变得容易。
(1)大根排序的基本思路
(1)首先，构建初始文件R[1.n]成一大堆，这是最初的无序区域。
其次，将关键字最大的记录R[1](即堆的顶部)与无序区域中的最后一条记录R[n]进行交换，从而得到新的无序区域R[1.n-1]和有序区域R[n]，并且满足R[1.n-1]。keyR[n]. key。
因为交换后的新根R[1]可能违反堆属性，当前无序区域R[1.n-1]应调整为堆。然后，记录R[1]中关键字最大的R[1].n-1]再次与该区间中的最后一个记录R[n-1]交换，从而获得新的无序区域R[1.n-2]和有序区域R[n-1.n]，并且仍然满足关系式R[1.n-2]。
……
直到无序区只有一种元素。
(2)大根堆排序算法的基本操作：
初始化操作：R[1.n]被构造为初始堆；
每次行程排序的基本操作：将当前无序区的顶部记录R[1]与区间的最后一条记录进行交换，然后将新的无序区调整为一个堆(也称为重构堆)。
注意：
(1)只需按n-1趟排序，选择较大的n-1个关键词，可以使文件逐渐有序增加。
hxsdgs堆排序与大根堆排序相似，只是排序结果递减且有序。堆排序与直接选择排序相反：在任何时候，堆排序中无序区域总是在有序区域之前，有序区域从原始向量末尾的后向前逐渐扩展到整个向量。
(3)堆排序算法：
void heap sport(SEQiast R)
{//堆栈和排序R[1.n]，并使用R[0]作为临时存储单元。
int I；
构建堆；//在初始反应器中构建R[1-n]
for(I=n；i1；I-){//堆叠并排序当前无序区域R[1.第n-1次旅行。
R[0]=R[1]；R[1]=R[I]；R[I]=R[0]；//用堆中的最后一条记录交换堆的顶部。
Heapify(R，1，I-1)；//重新调整R[1.i-1]到堆，只有R[1]可能违反堆属性。
} //endfor
} //HeapSort
(4)构建堆和堆函数的实现
因为初始堆的构造必须使用调整堆的操作，所以我们先讨论Heapify的实现。
健康功能思维方法
R [L. I]是每次排序开始前以R[1]为根的堆。在R[1]和R[i]交换之后，只有新的无序区域R[1]中R[1]的值.i-1]发生了变化，因此除了可能违反堆属性的R[1]之外，所有具有根节点的子树都是堆。因此，当调整后的间隔为r[低.高]，只需要调整以R[低]为根的树即可。
筛选方法的调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。具体的算法【参见教材】
②BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。
具体算法【参见教材】。
5、大根堆排序实例
对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见【动画演示】。
6、 算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。