本篇文章分成以下幾個章節 :
- 堆積樹(Heap tree)。
- 堆積排序法的原理。
- 堆積排序法的執行效能。
- javascript 演算法實作。
堆積樹 Heap Tree
再說明堆積排序排序前，我們需要先知道一個東西，那就是Heap Tree，它是二元樹(不知道的可以看筆者的這篇文章，不過我們在這篇中還是會簡單的複習)的一種，
那二元樹是啥 ? 就是長的和下圖一樣的東西，而二元樹有兩個比較嚴謹的定義如下。
1 . 每個節點最多有兩個子節點 2 . 子節點有左右之分
而其中，我們在這邊需要用的是完全二元樹Complete Binary Tree，它就是Heap Tree，它除了上面的定義外，還有第三個定義。
3 . 除了最後一階層之外的階層，都必預完全有左與右節點
它的樣子如下圖。
最大堆積 Max Heap
在了解完Heap Tree後，我們就要來知道，Max Heap是啥，它也是種堆積樹一種，不過它有個條件。
1 . 父節點的值大於子節點 2 . 樹根(root)一定是所有節點的最大值
根據以上的條件畫出的圖，大概如下。
我們這邊來看看下面幾張Max Heap產生過程的圖解。
首先我們會先將陣列轉換成Heap Tree。
然後我們會從最後的父節點，開始進行Max Heap判斷，然後再往前遞回。我們會先從09該節點進行判斷，由於09小於16，因此進行互換，結果如下圖。
接下來，我們在往回前一個父節點，11來進行判斷，因為該父節點值都大於子節點02與10因此不需要進行互換。結果如下圖。
最後再來判斷root，也就是最後一個父節點08，它下面兩個子節點11與16都比它大，因此，它選擇最大值16進行交換，然後08再於09進行比較，再進行交換，結果如下。
最後產生出的Max Heap結果如下。
堆積排序法的原理
在了解完上面的預備知識後，我們就可以開始了解堆積排序法的做法囉，它的流程如下。
前置作業
- 將陣列轉換成
Heap Tree。 - 在將
Heap Tree轉換成Max Heap
重複作業
- 將最上面的節點
root與最後面的節點交換位置。 - 再將
Tree轉換成Max Heap - 然後一直
re re re re這流程，直到完全排序完成。
下面我們將簡單用個範例，來說明他如下排序。首先我們有個要排序的陣列。
[08,14,16,10,9]
然後根據上述的前置作業先將它轉換成Max Heap。
[16,14,10,8,9]
接下來我們將要開始進行重複作業的步驟。首先，先將16(root)與09(最後結點)進行交換。其中下圖中的Swap(0,4)，代表著陣列位置為0與4的進資料進行交換。
然後接下來我們進行Max Heap的步驟，我們將從陣列位置0的資料9進行Max Heap，因為9小於14與10因此選擇較大者14進行交換。
再將14(root)與8(最後結點)進行交換，注意這時最後結點是8了喔。
然後在進行Max Heap，8小於9與10，選擇10進行換位。
進行10(root)與8(最後結點)交換。
再進行Max Heap。
最後在進行交換，然後完成。
注意，上述範例都是由小排到大，如果是要由大排到小的，需要將
Max Heap修改為Min Heap，也就是每個父元素值要小於子元素。
堆積排序法的執行效能
最好與最壞情況
O(nlogn)
javascript演算法實作
debugger;
/**
* swap
* swap datas location , ex [1,2] => swap(datas,0,1) => [2,1]
* @param datas
* @param i
* @param j
* @returns {undefined}
*/
function swap(datas, i, j) {
var temp = datas[i];
datas[i] = datas[j];
datas[j] = temp;
}
/**
* maxHeapIfy
* Create the max heap like this
* 6
* 4 5
* 1 2 3
*
* @param datas
* @param root
* @param length
* @returns {undefined}
*/
function maxHeapIfy(datas, root, length) {
var leftChild = root * 2 + 1;
var rightChild = root * 2 + 2;
var maxNode = -1;
// 如果左邊的子節點，大於父節點，則最大node設為左邊子節點
if (leftChild < length && (datas[leftChild] > datas[root])) {
maxNode = leftChild;
} else {
maxNode = root;
}
// 如果右邊的子節點，大於父節點，則最大node設為右邊子節點
if (rightChild < length && (datas[rightChild] > datas[maxNode])) {
maxNode = rightChild;
}
if (maxNode != root) {
swap(datas, root, maxNode);
maxHeapIfy(datas, maxNode, length);
}
}
/**
* heapSort
* heap sort datas
* @param datas
* @returns {undefined}
*/
function heapSort(datas) {
var start = Math.floor(datas.length / 2) - 1,
len = datas.length;
for (var i = start; i >= 0; i--) {
maxHeapIfy(datas, i, datas.length);
}
for (var j = len-1;j >=0;j--){
swap(datas,0,j);
maxHeapIfy(datas,0,j);
console.log(datas);
}
}
var datas = [8, 11, 9, 2, 10, 16];
heapSort(datas);