术语解释：
- 大根堆：树中所有非终端节点的值，不小于左右孩子节点的完全二叉树
- 建初堆：将r[1..n]调整为大根堆
- 调整堆：去掉堆顶元素后，将剩余元素调整成一个新的大根堆
代码实现：
include <iostream>
using namespace std;
void swap(int &a, int &b);
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void HeapSort(int *a, int n);
void CreateHeap(int *a, int n);
void AdjustHeap(int *a, int s, int m);
void AdjustHeap(int *a, int s, int m)
{
int temp = a[s]; //取出堆顶元素
for (int i = 2 * s; i <= m; i *= 2) //i从s的左孩子开始
{
if (i<m && a[i] < a[i + 1]) //i为大孩子的位置，i<m表示有有孩子
{
i++;
}
if (temp >= a[i]) //堆顶元素大于俩孩子，说明已经是堆了，结束
{
break;
}
a[s] = a[i]; //大孩子上去
s = i; //s为大孩子上去之前的位置
}
//现在已经得到了s，也就是堆顶元素的正确位置
a[s] = temp; //将堆顶元素丢进去
}
void CreateHeap(int *a, int n)
{
for (int i = n / 2; i > 0; i--)
{
AdjustHeap(a, i, n);
}
}
void HeapSort(int *a, int n)
{
CreateHeap(a, n); //建初堆
for (int i = n; i > 1; i--) //i一开始为最后一个元素的位置
{
swap(a[1], a[i]); //堆顶和最后一个元素交换
AdjustHeap(a, 1, i - 1); //将a[1..i-1]调整为大根堆
}
}
int main()
{
//下标从1开始
int a[9] = {-1, 45, 34, 78, 12, 34, 32, 29, 64};
int b[9] = {-1, 12, 29, 32, 34, 34, 45, 64, 78};
int n = 8;
HeapSort(a, n);
bool sorted = true;
for (int i = 1; i <= n; i++)
{
if (a[i] != b[i])
{
sorted = false;
break;
}
}
if (sorted)
{
cout << "true" << endl;
}
//打印排序后的数组
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << system("pause");
return 0;
}
参考资料：《数据结构（C语言版）》p221-p225
