本文实例讲述了C++实现堆排序算法的方法，相信对于大家学习数据结构与算法会起到一定的帮助作用。具体内容如下：
首先，由于堆排序算法说起来比较长，所以在这里单独讲一下。堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将L[n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。
一、堆的定义
堆的定义如下：n个关键字序列L[n]成为堆，当且仅当该序列满足：
①L(i) <= L(2i)且L(i) <= L(2i+1) 或者 ②L(i) >= L(2i)且L(i) >= L(2i+1) 其中i属于[1, n/2]。
满足第①种情况的堆称为小根堆（小顶堆），满足第②种情况的堆称为大根堆（大顶堆）。在大根堆中，最大元素存放在根结点中，且对任一非根结点，它的值小于或等于其双亲结点值。小根堆则恰恰相反，小根堆的根结点存放的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表示的大根堆：
二、构造初始堆
堆排序的关键就是构造初始堆。n个结点的完全二叉树中，最后一个结点是第n/2（向下取整）个结点的孩子。所以构造初始堆的流程是：对第n/2（向下取整）个结点为根的子树进行筛选（以大根堆为例，若根结点的关键字小于左右子女中关键字的较大者，则交换），使该子树成为堆。之后向前依次对从n/2-1到1的各结点为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不是，将左右子结点中较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。
由于在数组中下标从0开始，所以在堆中i的左子结点为2*i+1，右子结点为2*i+2。下面是将某个结点i向下调整建堆的算法实现：
void AdjustDown(ElementType A[], int i, int len)
{
ElementType temp = A[i]; // 暂存A[i]
for(int largest=2*i+1; largest<len; largest=2*largest+1)
{
if(largest!=len-1 && A[largest+1]>A[largest])
++largest; // 如果右子结点大
if(temp < A[largest])
{
A[i] = A[largest];
i = largest; // 记录交换后的位置
}
else
break;
}
A[i] = temp; // 被筛选结点的值放入最终位置
}
