Heap Sort 堆積排序法

Heap Sort 堆積排序法
Categories:
Tags:

複雜度

複雜度 Big O
最差時間複雜度 Worst-case time complexity Big O(n log n)
平均時間複雜度 Average-case time complexity Big theta (n log n)
最佳時間複雜度 Best-case time complexity Big omega (n log n)
空間複雜度 Space complexity Big O (1)

Heap 結構

  • 由上到下
  • 由左到右

陣列索引順序

陣列 [10, 6, 7, 5, 15, 17, 12] 會依序在 Heap 樹 由上到下及由左到右放置

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
陣列 10 6 7 5 15 17 12
索引位置 0 1 2 3 4 5 6

陣列數字演算法

節點 演算法
parent 母節點 (currentNumberIndex -1) / 2
left child 左節點 2 * currentNumberIndex + 1
right child 右節點 2 * currentNumberIndex + 2

計算 [10, 6, 7, 5, 15, 17, 12] 陣列中數字 6 的節點

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 6 的索引位置：1
節點 演算法 母節點索引位置 母節點索引位置數字
parent 母節點 (1 - 1) / 2 0 10
left child 左節點 2 * 1 + 1 3 5
right child 右節點 2 * 1 + 2 4 15

計算 [10, 6, 7, 5, 15, 17, 12] 陣列中數字 7 的節點

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 7 的索引位置：2
節點 演算法 母節點索引位置 母節點索引位置數字
parent 母節點 (2 - 1) / 2 0 10
left child 左節點 2 * 2 + 1 5 17
right child 右節點 2 * 2 + 2 6 12

Max Heap 比較流程

1. 從中間點找最大值

比較左右節點，確認是否有彼此節點大的數字，如果有的話則將此節點交換往上移動

中間節點：Math.floor(整數長度 / 2) = 7/2 = 3.5 = 3

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
  • 索引 3 數字 5
節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 3 + 1 7 找不到
right child 右節點 2 * 3 + 2 8 找不到

確認中間節點的左右節點，都比中間節點 數字 5 較小

而因為找不到 數字 5 的左右節點，所以確認 數字 5 是這三個節點中最大

2. 往中間點左方移動，繼續找最大值

索引 3 數字 5的左方是索引 2 數字 7

      10
    /    \
   6      7
 /  \    /  \
5   15  17  12
節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 2 + 1 5 17
right child 右節點 2 * 2 + 2 6 12

這邊會找到左右節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      10
    /    \
   6      17
 /  \    /  \
5   15  7   12

整個陣列會從 [10, 6, 7, 5, 15, 17, 12] 變成 [10, 6, 17, 5, 15, 7, 12]

陣列 10 6 17 5 15 7 12
索引位置 0 1 2 3 4 5 6

3. 比較完成左方移動，繼續找最大值

索引 2 數字 17的左方是索引 1 數字 6

      10
    /    \
   6      17
 /  \    /  \
5   15  7   12
節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 1 + 1 3 5
right child 右節點 2 * 1 + 2 4 15

這邊會找到右節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      10
    /    \
  15      17
 /  \    /  \
5    6  7   12

整個陣列會從 [10, 6, 17, 5, 15, 7, 12] 變成 [10, 15, 17, 5, 6, 7, 12]

陣列 10 15 17 5 6 7 12
索引位置 0 1 2 3 4 5 6

4. 比較完成左方移動，繼續找最大值

索引 1 數字 15的左方是索引 0 數字 10

      10
    /    \
  15      17
 /  \    /  \
5    6  7   12
節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 0 + 1 1 15
right child 右節點 2 * 0 + 2 2 17

這邊會找到右節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      17
    /    \
  15      10
 /  \    /  \
5    6  7   12

整個陣列會從 [10, 15, 17, 5, 6, 7, 12] 變成 [17, 15, 10, 5, 6, 7, 12]

陣列 17 15 10 5 6 7 12
索引位置 0 1 2 3 4 5 6

5. 比較最後交換的數字

最後交換的數字是索引 2 數字 10

      17
    /    \
  15      10
 /  \    /  \
5    6  7   12
節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 2 + 1 5 5
right child 右節點 2 * 2 + 2 6 12

這邊會找到右節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      17
    /    \
  15      12
 /  \    /  \
5    6  7   10

整個陣列會從 [17, 15, 10, 5, 6, 7, 12] 變成 [17, 15, 12, 5, 6, 7, 10]

陣列 17 15 12 5 6 7 10
索引位置 0 1 2 3 4 5 6

最後就會完整的建立整個 Max Heap Tree，確定母節點的數字都是大於子節點

6. 從最後的節點開始排序 Heap 陣列

現在整個 Max Heap 陣列，可以確認的是第 1 個數字一定是整個陣列中最大的

所以為了排序需要將這個數字移動到陣列最後

      10
    /    \
  15      12
 /  \    /  
5    6  7   17

將陣列中最大數字 17 移動到最後之後，就不再檢查最後的索引數字，所以將數字 17 移出整個 Max Heap Tree 的檢查

但是將原本最後的索引數字 10 移動到第 1 個數字後，整個 Max Heap 陣列 的邏輯又被打破，為了維持狀況，必須要母節點的數字都是大於子節點

所以可以從 索引 0 數字 10 開始，比較左右節點

節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 0 + 1 1 15
right child 右節點 2 * 0 + 2 2 12

這邊會找到左節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      15
    /    \
  10      12
 /  \    /  
5    6  7   17

再來繼續檢查移動後的 索引 1 數字 10，確定是否有滿足 Max Heap Tree

節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 1 + 1 3 5
right child 右節點 2 * 1 + 2 4 6

最後可以確認，左右節點都比 數字 10 還要小，這樣就又產生出了一個新的 Max Heap Tree，母節點的數字都是大於子節點

7. 從最後的檢查節點往左移動，繼續排序 Heap 陣列

現在整個 Max Heap 陣列，可以確認的是第 1 個數字一定是整個陣列中最大的

所以為了排序需要將這個數字移動到陣列最後

      7
    /    \
  10      12
 /  \      
5    6  15   17

將陣列中最大數字 15 移動到最後之後，就不再檢查最後的索引數字，所以將數字 15 移出整個 Max Heap Tree 的檢查

但是將原本最後的索引數字 7 移動到第 1 個數字後，整個 Max Heap 陣列 的邏輯又被打破，為了維持狀況，必須要母節點的數字都是大於子節點

所以可以從 索引 0 數字 7 開始，比較左右節點

節點 演算法 母節點索引位置 母節點索引位置數字
left child 左節點 2 * 0 + 1 1 10
right child 右節點 2 * 0 + 2 2 12

這邊會找到左右節點比母節點還大，將最大的子節點移動到母節點，那這整棵 Heap 樹會變成

      12
    /    \
  10      7
 /  \      
5    6  15   17

再來繼續檢查移動後的 索引 2 數字 7，確定是否有滿足 Max Heap Tree

而現在因為 索引 2 數字 7 沒有其他的子節點了，所以這樣就又產生出了一個新的 Max Heap Tree，母節點的數字都是大於子節點

8. 重複整個流程，從最後的檢查節點往左移動，繼續排序 Heap 陣列

整個 Tree 的比較流程會變成這樣

最大 數字 12 與 數字 6 交換，數字 12 移出檢查 Max Heap Tree

      6
    /    \
  10      7
 /        
5   12  15   17

數字 6 檢查是否滿足 Max Heap Tree，比較後調整 Max Heap Tree

      10
    /    \
  6       7
 /        
5   12  15   17

最大 數字 10 與 數字 5 交換，數字 10 移出檢查 Max Heap Tree

      5
    /    \
  6       7

10  12  15   17

數字 5 檢查是否滿足 Max Heap Tree，比較後調整 Max Heap Tree

      7
    /    \
  6       5

10  12  15   17

最大 數字 7 與 數字 5 交換，數字 7 移出檢查 Max Heap Tree

      5
    /    
  6       7

10  12  15   17

數字 5 檢查是否滿足 Max Heap Tree，比較後調整 Max Heap Tree

      6
    /    
  5       7

10  12  15   17

最大 數字 6 與 數字 5 交換，數字 6 移出檢查 Max Heap Tree

      5

  6      7

10  12  15   17

這樣整個移動到最後，就可以得到一個排序的陣列 [5, 6, 7, 10, 12, 15, 17]

演算法

1. 解析數字陣列轉換成 Max Heap Tree

從整個陣列中的中間位置開始做 Max Heap Tree 檢查 Math.floor(numberListLength / 2)

然後往陣列左側掃描整個 Heap Tree

確保陣列第一個數字是整個 Max Heap Tree 最大的，並保持母節點的數字都是大於子節點

節點 演算法
parent 母節點 (currentNumberIndex -1) / 2
left child 左節點 2 * currentNumberIndex + 1
right child 右節點 2 * currentNumberIndex + 2

A. 比較自己級左右節點，把最大的節點移動到母節點

B. 當節點有做異動，繼續對此節點做 Heap Tree

確認這個節點跟母節點的關係，也可以保持母節點的數字都是大於子節點

持續做到 Heap Tree 的第一個陣列數字

當結束後就可以確保第一個數字一定是整個 Heap Tree 最大的數字

2. 將數字由大到小依序交換至後方做排序

建立完 Max Heap Tree 後，第一個元素一定是最大的，將第一個元素最大數字與最後方的元素交換

這樣整個陣列中的最後方往前方，會是由大到小排序

最後方元素確保是整個 Heap Tree 最大的數字後，將此元素移除整個 Heap Tree 不再檢查

3. 重新建立最新的 Max Heap Tree 平衡樹

原本最後方的元素因為被交換移動到第一個元素了，所以可能會破壞整個 Max Heap Tree 的原則，無法保持母節點的數字都是大於子節點

所以重新對剩餘的數字建立 Max Heap Tree，將剩餘數字最大的數字移動到後來 Max Heap Tree 的第一個元素

4. 持續對剩餘 Heap Tree 做 2~3 的步驟，直到比較到剩餘一個元素

元素會由大到小，持續地放在後方，持續的移除不在 Heap Tree 範圍，直到整個 Max Heap Tree 剩 1 個元素

那最後整個陣列就會變成 由小到大 排序的陣列

程式

TypeScript

function heapify(numberList: number[], heapAvailableLength: number, currentNode: number):void {
    // 計算左節點位置
    const leftChildNode = currentNode * 2 + 1;
    // 計算右節點位置
    const rightChildNode = currentNode * 2 + 2;

    // 先預設最大的節點是自己
    let maxNode = currentNode;

    if (leftChildNode < heapAvailableLength && numberList[leftChildNode] > numberList[maxNode]) {
        // 如果「左節點」在 Heap 允許的範圍內
        // 且「左節點數字」大於「目前最大節點數字」
        // 將左節點設定為目前最大節點
        maxNode = leftChildNode;
    }

    if (rightChildNode < heapAvailableLength && numberList[rightChildNode] > numberList[maxNode]) {
        // 如果「右節點」在 Heap 允許的範圍內
        // 且「右節點數字」大於「目前最大節點數字」
        // 將右節點設定為目前最大節點
        maxNode = rightChildNode;
    }

    // 如果左右兩邊有任何一個比 node 大的話
    if (maxNode !== currentNode) {
        // 就把兩個互換
        [numberList[currentNode], numberList[maxNode]] = [numberList[maxNode], numberList[currentNode]];

        // 接著繼續對目前最大節點做 heapfiy
        heapify(numberList, heapAvailableLength, maxNode);
    }
}

function heapSort(numberList: number []): number[] {
    // 建立 max heap
    const numberListLength = numberList.length;
    // 起始 Heap 檢查點
    let beginHeapCheckPointer = Math.floor(numberListLength / 2);
    // 建立 Heap Tree
    for (let i = beginHeapCheckPointer; i >= 0; i--) {
        heapify(numberList, numberListLength, i);
    }

    // 排序
    for (let i = numberListLength - 1; i > 0; i--) {
        // 從最後陣列元素位置開始，持續將第一個元素（最大元素）轉移到最後方，讓越大的數字放在後方
        [numberList[0], numberList[i]] = [numberList[i], numberList[0]];
        // 排除後方交換的元素，對第一個節點做剩餘數字的 Max Heap Tree
        heapify(numberList, i, 0);
    }

    return numberList;
}

let items = [10, 6, 7, 5, 15, 17, 12];

console.log(heapSort(items));

參考資料