堆排序與快速排序，歸並排序一樣都是時間復雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先講解下什麼是數據結構中的二叉堆。
二叉堆是完全二叉樹或者是近似完全二叉樹。
二叉堆滿足二個特性：
1．父結點的鍵值總是大於或等於（小於或等於）任何一個子節點的鍵值。
2．每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。
當父結點的鍵值總是大於或等於任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小於或等於任何一個子節點的鍵值時為最小堆。下圖展示一個最小堆：
由於其它幾種堆（二項式堆，斐波納契堆等）用的較少，一般將二叉堆就簡稱為堆。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
一般都用數組來表示堆，i結點的父結點下標就為(i – 1) / 2。它的左右子結點下標分別為2 * i + 1和2 * i + 2。如第0個結點左右子結點下標分別為1和2。
下面先給出《數據結構C++語言描述》中最小堆的建立插入刪除的圖解，再給出本人的實現代碼，最好是先看明白圖後再去看代碼。
《數據結構 C++ 語言描述》(Data Structures C++ ) PDF 下載地址：http://www.linuxidc.com/Linux/2014-09/107319.htm
每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，現在的任務是將這個新數據插入到這個有序數據中——這就類似於直接插入排序中將一個數據並入到有序區間中，對照《直接插入排序的三種實現》不難寫出插入一個新數據時堆的調整代碼：
// 新加入i結點 其父結點為(i - 1) / 2
void MinHeapFixup(int a[], int i)
{
int j, temp;
temp = a[i];
j = (i - 1) / 2; //父結點
while (j >= 0)
{
if (a[j] <= temp)
break;
a[i] = a[j]; //把較大的子結點往下移動,替換它的子結點
i = j;
j = (i - 1) / 2;
}
a[i] = temp;
}
更簡短的表達為：
void MinHeapFixup(int a[], int i)
{
for (int j = (i - 1) / 2; j >= 0 && a[i] > a[j]; i = j, j = (i - 1) / 2)
Swap(a[i], a[j]);
}
插入時：
//在最小堆中加入新的數據nNum
void MinHeapAddNumber(int a[], int n, int nNum)
{
a[n] = nNum;
MinHeapFixup(a, n);
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-09/107318p2.htm