4 months ago
  • 堆積樹(Heap tree)。
  • 堆積排序法的原理。
  • 堆積排序法的執行效能。
  • javascript 演算法實作。

堆積樹 Heap Tree

再說明堆積排序排序前,我們需要先知道一個東西,那就是Heap Tree,它是二元樹(不知道的可以看筆者的這篇文章,不過我們在這篇中還是會簡單的複習)的一種,
那二元樹是啥 ? 就是長的和下圖一樣的東西,而二元樹有兩個比較嚴謹的定義如下。

  • 每個節點最多有兩個子節點
  • 子節點有左右之分

而其中,我們在這邊需要用的是完全二元樹Complete Binary Tree,它就是Heap Tree,它除了上面的定義外,還有另外一個。它的樣子大至上如下圖。

  • 除了最後一階層之外的階層,都必預完全有左與右節點

最大堆積 Max Heap

在了解完Heap Tree後,我們就要來知道,Max Heap是啥,它也是種堆積樹一種,不過它有個條件。

  • 父節點的值大於子節點
  • 樹根(root)一定是所有節點的最大值

根據以上的條件畫出的圖,大概如下。

我們這邊來看看下面幾張Max Heap產生過程的圖解。

首先我們會先將陣列轉換成Heap Tree

然後我們會從最後的父節點,開始進行Max Heap判斷,然後再往前遞回。我們會先從09該節點進行判斷,由於09小於16,因此進行互換,結果如下圖。

接下來,我們在往回前一個父節點,11來進行判斷,因為該父節點值都大於子節點02與10因此不需要進行互換。結果如下圖。

最後再來判斷root,也就是最後一個父節點08,它下面兩個子節點11與16都比它大,因此,它選擇最大值16進行交換,然後08再於09進行比較,再進行交換,結果如下。

最後產生出的Max Heap結果如下。

堆積排序法的原理

在了解完上面的預備知識後,我們就可以開始了解堆積排序法的做法囉,它的流程如下。

前置作業

  1. 將陣列轉換成Heap Tree
  2. 在將Heap Tree轉換成Max Heap

重複作業

  1. 將最上面的節點root與最後面的節點交換位置。
  2. 再將Tree轉換成Max Heap
  3. 然後一直re re re re這流程,直到完全排序完成。

下面我們將簡單用個範例,來說明他如下排序。首先我們有個要排序的陣列。

[08,14,16,10,9]

然後根據上述的前置作業先將它轉換成Max Heap

[16,14,10,8,9]

接下來我們將要開始進行重複作業的步驟。首先,先將16(root)09(最後結點)進行交換。其中下圖中的Swap(0,4),代表著陣列位置為04的進資料進行交換。

然後接下來我們進行Max Heap的步驟,我們將從陣列位置0的資料9進行Max Heap,因為9小於14與10因此選擇較大者14進行交換。

再將14(root)8(最後結點)進行交換,注意這時最後結點是8了喔。

然後在進行Max Heap8小於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);

參考資料

← 排序之選擇排序法(Selection Sort) 排序之快速排序法(Quick Sort) →
 
comments powered by Disqus