這裡先簡單說下最大堆的基本性質： 最大堆一定是完全二叉樹 當父節點為 n 時，左孩子為 n 2 + 1，右孩子為 n 2 + 2 當孩子為 n 時，其父節點為： (n 1) / 2 這一點很重要，在後面初始化的時候會用到 父節點大於等於左孩子和右孩子，但左孩子不一定大於右孩子 瞭解以上基本性質之後， ...
這裡先簡單說下最大堆的基本性質：
- 最大堆一定是完全二叉樹
- 當父節點為 n 時，左孩子為 n * 2 + 1，右孩子為 n * 2 + 2
- 當孩子為 n 時，其父節點為： (n - 1) / 2 ----> 這一點很重要，在後面初始化的時候會用到
- 父節點大於等於左孩子和右孩子，但左孩子不一定大於右孩子
瞭解以上基本性質之後，就可以先看一下如何對一個序列做最大堆的初始化。
最大堆的構造
思路：過程就像冒泡一樣，從最序號最大的父節點開始，查看是否滿足最大堆，如果不滿足，則調整（調整之後，還要查看被調整的節點是否依然滿足最大堆性質，如果不滿足，則需要往下遍歷調整，這部分在後面的舉例中會有說明），如果滿足，則繼續查看前一個父節點是否滿足，直接最終的0節點。
例如：這裡有個數組：x[] = {2 5 3 9 7 1 6}，則對應樹為：
該序列長度為7，最大下標為6，則最大的父節點下標就是: (6 - 1)/ 2 是2（基本性質第三條），對應的數值是3，
他的左孩子是1，右孩子是6，右孩子比父節點大，所以應該調整一下這兩個節點，得到：
該節點調整完之後，再查看前一個父節點，下標為1，對應的數值為5，
他的左孩子是9，右孩子是7，不滿足，所以父節點應該與左孩子進行交換，得到:
繼續往前，再前面一個父節點下標為0，數值為2，左孩子是9，右孩子是6，不滿足最大堆，父節點與左孩子交換，得到：
交換之前，左孩子為9，現在左孩子為2，導致這個左孩子不滿足最大堆性質，因為這個左孩子的左孩子大於左孩子，所以，這裡就出現了上面括弧中所說的：調整完之後，還要查看被調整的節點是否依然滿足最大堆的性質。
這裡還要對調整之後的節點繼續調整：
至此，一個最大堆就初始化完成了！
堆排序
其實，明白了最大堆怎麼構造出來的之後，堆排序就很容易了。
想一想，最大堆構造出來之後，其實就直接得到了最大值：x[0]，
如果把 x[0] 與最後一個數字交換一下，然後對剩下的數字重新按之前的方法構造一下，不就找到了第二大的數字了嗎？
此時第二大的數字就是x[0]，把它與剛剛參加排序的最後的一個數字交換一下，然後再對剩下的數字排序一下，就可以得到第三大的數字，
這麼一直迴圈，就可以把當前數組排序完成了。
接著剛剛的那個例題，先把9與參與排序的最後一個數字對換，得到：
此時參與排序的，就只有：3，7，6，5，2，1。
因為x[0]被調整了，所以要查看x[0]是否依然最大堆性質，顯然是不滿足的，所以繼續調整x[0]，得到:
x[0]與x[1]互換之後，導致被調整的x[1]又不滿足最大堆，那就再調整一下：
現在整個樹都滿足最大堆了，也就得到了現在參與排序的最大值x[0]為7，
所以，x[0]與當前參與排序的最後一位交換，得到：
此時參與排序的，只有：1，5，6，3，2。
按照上面步驟再次迴圈，這裡就不寫了，直接放圖：
上代碼：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 列印數組
void print(int *array, int len)
{
for (int i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
// 交換兩個數值
void swap(int *array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
return;
}
// 對當前父節點進行排序
// 查看該父節點是否滿足最大堆，如果不滿足則調整子節點
void sort (int *array, int father, int len)
{
for (int lchild =father*2+1; lchild<len; lchild=father*2+1)
{
int k = lchild; // 先用k指向左孩子
int rchild = lchild + 1;
if ((rchild < len) && (array[rchild] > array[lchild]))
{
k = rchild; // 如果有右孩子，且右孩子比左孩子還大，則更新k
}
// 這裡的k，指向了左右孩子中較大的那個
if (array[k] > array[father])
{
swap(array, k, father); // 交換父親和孩子的數值
father = k; // 這裡就是查看被調整之後的節點k，是否依然滿足最大堆
}
else
{
break; // 當前節點不需要被調整
}
}
return;
}
int main(void)
{
int x[] = {2,5,3,9,7,1,6};
int len = sizeof(x)/sizeof(int);
print(x, len); // 先輸出原始序列
// 最大子節點下標為len-1，所以它的父節點是 (len-1-1) / 2
for (int i = (len - 2)/2; i>=0; i--)
{
sort(x, i, len);
}
print(x, len); // 輸出初始化之後的最大堆
for (int i=(len-1); i>0; i--)
{
swap(x, 0, i); // 把最大的一個值放到末尾，然後對剩餘的數組進行排序
sort(x, 0, i);
}
print(x, len); // 輸出排序之後的序列
return 0;
}
最終輸出為：
2 5 3 9 7 1 6
9 7 6 5 2 1 3
1 2 3 5 6 7 9 
