术语解释：

• 大根堆：树中所有非终端节点的值，不小于左右孩子节点的完全二叉树
• 建初堆：将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