堆排序的思想：
每次构造一个堆，将堆的根节点添加到有序序列中。
其中，r1 为最大值
与最后一个元素 rn 交换
对无序序列进行堆调整
得到最大的值
继续进行交换，重复步骤，即可得到有序序列。
堆的定义
堆是具有下列性质的完全二叉树:
每个结点的值都小于或等于其左右孩子结点的值(称为小根堆) 或 每个结点的值都大于或等于其左
右孩子结点的值(称为大根堆)。
小根堆：
特点：
1、小根堆的根节点是所有节点的最小者。
2、较小的结点靠近根节点，但不绝对。
大根堆：
特点：
1、大根堆的根节点是所有节点的最大者。
2、较大的结点靠近根节点，但不绝对。
堆和序列的关系
采用顺序存储，编号后得
将堆用顺序存储结构来存储，则堆对应一组序列。
符合完全二叉树的性质：
堆调整
条件：左子树，右子树均为堆
从上向下进行处理大根
关键问题（1）：由无序序列建立一个堆
假设：sift（r，k，end）函数为堆调整函数，其中k为要筛选节点的编号，end为堆中最后一个节点的编号。
注：最后一个结点的序号是n，则最后一个分支结点即为结点n的双亲，序号为n/2.
for (k = n/2; k >= 1; k--)
sift(r,k,n);
当k=4时，
K=3时，
K=2时，
K=1时，
经过sift函数的调用，完成大根堆。
void sift(int r[], int k, int end)
{
int i = k, j = 2 * i;
int m = 0;
while (j <= end)
{
if (j < end && r[j] < r[j + 1])
j++;
if (r[i] < r[j])
{
m = r[i];
r[i] = r[j];
r[j] = m;
}
i = j;
j = 2 * i;
}
}关键问题（2）处理堆顶记录
解决方法：
第k次处理堆顶是将堆顶记录r[1]与序列中第n-k+1个记录r[n-k+1]交换。
关键问题（3）调整剩余记录，成为一个新堆
解决办法：
sift（r，1，n-k）
void heapsort(int r[], int n)
{
for (int k = n / 2; k >= 1; k--)
sift(r, k, n); // 初建堆
for (k = 1; k < n; k++)
{
r[0] = r[1];
r[1] = r[n - k + 1];
r[n - k + 1] = r[0];
sift(r, 1, n - k); // 重建堆
}
}
