術(shù)語解釋：

• 大根堆：樹中所有非終端節(jié)點的值，不小于左右孩子節(jié)點的完全二叉樹
• 建初堆：將r[1..n]調(diào)整為大根堆
• 調(diào)整堆：去掉堆頂元素后，將剩余元素調(diào)整成一個新的大根堆

代碼實現(xià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]) //堆頂元素大于倆孩子，說明已經(jīng)是堆了，結(jié)束
{
break;
}
a[s] = a[i]; //大孩子上去
s = i; //s為大孩子上去之前的位置
}

//現(xiàn)在已經(jīng)得到了s，也就是堆頂元素的正確位置
a[s] = temp; //將堆頂元素丟進(jìn)去

}

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]調(diào)整為大根堆
}
}

int main()
{
//下標(biāo)從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;
}

//打印排序后的數(shù)組
for (int i = 1; i <= n; i++)
{
    cout << a[i] << " ";
}

cout << system("pause");
return 0;

}

參考資料：《數(shù)據(jù)結(jié)構(gòu)（C語言版）》p221-p225