[排序演算法]Heap Sort — 堆積排序法

heap sort 的原理是採用 max heap 這種資料結構來做排序，max heap 是一種 binary tree，每個節點都會比自己的子節點還大，因此根節點會是最大值，讓我們先來理解如何實作一個 max heap 吧!假設現在有一個排序是亂的 binary tree 如下圖

1. 先從右邊的 subtree 開始，如果 subtree 的父節點不是最大值就跟子節點做交換，7 跟 9 交換

2. 15 已是最大值，所以不用跟子節點交換

3. 16 為最大值，故與 3 做交換

4. 12 與 8 做交換

5. 當最下層的節點都遍歷完了，就輪到上面一層，15 與 11 交換，不過這時候會發現一個問題，交換過後 11, 10 ,14 這個 subTree 並不是一個 max heap，因此還要再做一次交換

6. 因此 14 與 11 交換，每次交換的時候都要檢查下一層的值是否有比當前的值還大，有的話當前值就要跟較大值對調位置

這樣依序的交換過一輪最後就會獲得一個 max-heap🎉

理解了 max-heap 的運作原理之後，就可以來探討如何用 max-heap 做 heap sort 了。

1. 先將根節點(16)與 leaf node 最右邊的節點(4)做交換，此時 4 會在根節點的位置，16 會跑到右下角，接著移除右下角的節點並取出 16 放在下方，這時會發現 4 並不是這整顆樹裏面的最大值，因此 4 要向下交換

2. 交換過後如果發現下面還有比自己更大的值就要一直交換下去，最後 4 來到了這個位置

3. 這時會發現 15 已經是整個 max-heap 的最大值，於是跟 leaf node 下層最右邊的節點 7 做交換，再把 15 從節點中抽離出來，接下來就是一直不斷的重複這個動作

如果還是覺得有點抽象的話，可以參考 heap sort 的流程的 gif，應該可以幫助理解，畫面中的 heapify 指的是將根節點一路向下交換的過程

用 js 實作 max heap

首先先將 tree 轉換成陣列，由上到下將每個節點取出的話 ，可以得到一個陣列[5, 13, 11, 8, 3, 15, 7, 12, 2, 16, 6, 10, 14, 9, 4]

1. 需要先建立一個 maxHeap，透過起始點的公式(Math.floor(heapSize / 2))算出 7，先從 index 7 (數字 12)開始，但因為 12 沒有子節點，所以往 index 6 移動(數字 7)，開始執行 heapify
2. 經過不斷的 heapify，最大值會移動到根節點
3. 根節點與 left node 最右邊的節點做交換，將最大值取出，移除 left node 最右邊的節點
4. 此時根節點並非最大值，需要再次進行步驟 2，不斷重複…
5. 直到全部節點都取出，陣列就排序完成了

用 js 實作 heap sort

const createMaxheap = (arr, heapSize) => {
  //從 Math.floor(heapSize / 2)這個節點開始檢查
  for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
    maxHeapify(arr, i, heapSize);
  }
};
const maxHeapify = (arr, i, heapSize) => {
  let largest;
  let left = i * 2 + 1; //取自己的左子節點
  let right = i * 2 + 2; //取自己的右子節點
  //檢查subtree裡面 誰是最大值?
  largest = left <= heapSize && arr[left] > arr[i] ? left : i;
  if (right <= heapSize && arr[right] > arr[largest]) {
    largest = right;
  }

  //如果subtree的parent不是最大的 就持續向下交換
  if (largest != i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    maxHeapify(arr, largest, heapSize);
  }
};

const heapSort = (arr) => {
  let heapSize = arr.length - 1;
  //先建立maxHeap
  createMaxheap(arr, heapSize);
  for (let i = arr.length - 1; i >= 0; i--) {
    //將leaf node最右邊那個跟根節點交換
    [arr[0], arr[i]] = [arr[i], arr[0]];
    //節點取出後 heapSize-1
    heapSize -= 1;
    //此時根節點並非最大值 需要執行maxHeapify
    maxHeapify(arr, 0, heapSize);
  }
  return arr;
};

heapSort([5, 13, 11, 8, 3, 15, 7, 12, 2, 16, 6, 10, 14, 9, 4]);

不得不說 heap sort 是我覺得最難理解的排序演算法 ，需要反覆消化很多次才能理解 😅

時間複雜度

👍 在最差的情況下，時間複雜度是 O(n log n)

👎 在最佳的情況下，時間複雜度是 O(n log n)

🤚 在平均情況下，時間複雜度為 O(n log n)