堆是一棵順序存儲的完全二叉樹丈甸。
其中每個結(jié)點(diǎn)的關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字线得，這樣的堆稱為小根堆够话。
其中每個結(jié)點(diǎn)的關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字蓝翰，這樣的堆稱為大根堆。
如上圖所示女嘲，序列R{3, 8, 15, 31, 25}是一個典型的小根堆畜份。
舉例來說，對于n個元素的序列{R0, R1, ... , Rn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時欣尼，稱之為堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
堆排序要點(diǎn)
（1）根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個完全二叉樹爆雹，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）。
（2）每次交換第一個和最后一個元素愕鼓，輸出最后一個元素（最大值）钙态，然后把剩下元素重新調(diào)整為大根堆。
當(dāng)輸出完最后一個元素后菇晃，這個數(shù)組已經(jīng)是按照從小到大的順序排列了册倒。
先通過詳細(xì)的實(shí)例圖來看一下，如何構(gòu)建初始堆磺送。
設(shè)有一個無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }驻子。
構(gòu)造了初始堆后，我們來看一下完整的堆排序處理：
還是針對前面提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來加以說明册着。
先給初始堆做個排序拴孤，如圖
根據(jù)二叉樹性質(zhì)：
如果一棵樹有n個節(jié)點(diǎn)的完全二叉樹，
如果2i+1>n, 則節(jié)點(diǎn)i無左孩子甲捏，i為葉子節(jié)點(diǎn)演熟，否則，左孩子節(jié)點(diǎn)是2i+1.
如果2i+2>n, 則節(jié)點(diǎn)i無由孩子，i為葉子節(jié)點(diǎn)芒粹，否則兄纺，右孩子節(jié)點(diǎn)是2i+2.
代碼實(shí)現(xiàn)
public static void heapSort (int[] list) {
// 循環(huán)建立初始堆
for (int i=list.length/2-1; i>=0; i--) {
HeapAdjust(list, i, list.length);
}
// 進(jìn)行n-1次循環(huán)，完成排序
for (int i=list.length-1; i>0; i--) {
//最后一個元素和第一元素進(jìn)行交換
swap(list, 0, i);
//繼續(xù)構(gòu)建堆
HeapAdjust(list, 0, i);
}
}
public static void HeapAdjust(int[] list, int parent, int len) {
//temp保存當(dāng)前父節(jié)點(diǎn)
int temp = list[parent];
//根據(jù)二叉樹性質(zhì)化漆，獲取左子樹
int child = 2 * parent + 1;
while (child < len) {
//判斷是否有右子樹估脆，如果大于左子樹，選取右子樹節(jié)點(diǎn)
if (child + 1 < len && list[child] < list[child+1]) {
child++;
}
//如果父節(jié)點(diǎn)大于孩子節(jié)點(diǎn)座云，跳出循環(huán)
if (temp > list[child]) {
break;
}
//把孩子節(jié)點(diǎn)賦值給父節(jié)點(diǎn)疙赠，此時父節(jié)點(diǎn)和孩子節(jié)點(diǎn)值一樣
list[parent] = list[child];
parent = child;
//繼續(xù)選取左孩子節(jié)點(diǎn)向下篩選
child = 2*child + 1;
}
list[parent] = temp;
}
public static void swap(int[] list, int i, int j) {
int temp = list[j];
list[j] = list[i];
list[i] = temp;
}
public static void main(String[] args) {
int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
heapSort(list);
for (int i=0; i<list.length; i++) {
System.out.print(list[i] + ", ");
}
}
輸出結(jié)果：
Heap sort:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
時間復(fù)雜度是：O(nlogn)
