堆積排序（Heap Sort）

堆積排序（heap sort）

使用「完整二元樹（complete binary tree）」這種資料結構，可能為「最大堆積（max heap）」或「最小堆積（min heap）」，使資料依照目標順序由根至葉排列，再將根與最末端節點的值對調，以便一一取出目標資料值進行排序。

1. 最大堆積（max heap）：對於每個「子樹」而言，「根」的資料必為最大；資料值大小由根至葉遞減。
2. 最小堆積（min heap）：對於每個「子樹」而言，「根」的資料必為最小；資料值大小由根至葉遞增。

「max heap」與「min heap」範例

在以下範例中，皆以「max heap」為例。

圖示

堆積排序共可分為下列三大步驟，不斷循環：

BUILD-MAX-HEAP()

從第 Math.floor((arr.length/2)) 項到根（第 0 項），一一使每棵子樹都變成「max heap」，最終整棵樹都變成「max heap」。

MAX-HEAPIFY()

為建立「max-heap」的過程。在每棵子樹內比較，如果最大的值不在根，就把最大的值換到根、原本在根的值往下換，使子樹成為「max-heap」；透過遞迴使每棵子樹都變成「max-heap」後，整棵樹即變成「max-heap」。

HEAP-SORT()

建立「max-heap」後，把整棵樹的最大值由根換到當下的最後一個節點，節點由第 (arr.length-1) 項往回到第 0 項會由大而小完成排序，這些已經完成排序的節點即排除於下一輪要排序的範圍之外。

在新的待排序範圍中，先以「MAX-HEAPIFY(0)」讓整棵樹變回「max-heap」，再持續執行「根與最末端節點對換」、「移除最末端已排序節點」的過程，待第 0 項也執行完畢時，整個陣列即從尾到頭由大而小完成排序，若從頭看就是從小排到大的陣列。

範例圖示

現假設有一陣列 [2,6,3,5,4,1,7]，用二元樹表示如下：

透過「max heap」實現堆積排序，我們可將這個陣列改成由大到小依序排列。

第一輪循環

1. BUILD-MAX-HEAP()：先比較下層子樹，確保每個子樹都是「max heap」。
2. MAX-HEAPIFY()：右子樹中右葉的值最大，因此將右葉與根的值互換；左子樹不需調整即為「max heap」。

1. BUILD-MAX-HEAP()：比較上層子樹，確保上層子樹也是「max heap」。
2. MAX-HEAPIFY()：因最大值在右葉，將右葉的值與根互換。

1. MAX-HEAPIFY()：上層子樹調換完成後，下層右子樹的最大值在右葉，因此再次將右葉與根的值互換。

調換完成後，二元樹即形成「max heap」。

HEAP-SORT()：將根與最末端節點的值互換，使最大值變成在最末端。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度減 1。

第二輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：此時新的待排序範圍並不是「max heap」，應將根的值一路往下換，直到每棵子樹的根都是該子樹的最大值為止。


此時待排序範圍又回到「max heap」。

HEAP-SORT()：再將根的值與待排序範圍最末端節點的值互換。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度再減 1。

第三輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：此時待排序範圍並不是「max heap」，應將根的值一路往下換，直到每棵子樹的根都是該子樹的最大值為止。


此時待排序範圍又回到「max heap」。

HEAP-SORT()：將根的值與最末端節點的值互換。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度再減 1。

第四輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：此時待排序範圍並不是「max heap」，應將根的值一路往下換，直到每棵子樹的根都是該子樹的最大值為止。


此時待排序範圍又回到「max heap」。

HEAP-SORT()：再將根的值與最末端節點的值互換。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度再減 1。

第五輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：此時待排序範圍並不是「max heap」，應將最大的值往上換。

此時待排序範圍又回到「max heap」。

HEAP-SORT()：因為要將最大值排入陣列，要再將根的值跟右葉對調。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度再減 1。

第六輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：此時待排序範圍並不是「max heap」，應將最大的值往上換。

此時待排序範圍又回到「max heap」。

HEAP-SORT()：因為要取出最大值，要再將根與最末端節點的值互換。

HEAP-SORT()：最末端節點完成排序，將待排序陣列長度再減 1。

第七輪循環

BUILD-MAX-HEAP()+MAX-HEAPIFY()：最後剩下一個節點，待排序範圍直接就是「max heap」。

HEAP-SORT()：將根與最末端節點的值互換，但因為只剩最後一個節點，所以是根自己的值跟自己互換。

最後得從頭到尾為由小到大的陣列。

完成排序之二元樹，寫成陣列為 [1,2,3,4,5,6,7]

偽代碼&說明

「堆積排序」的偽代碼分為三個部分，若以「將陣列由小到大排序」為目標，第一部分的「BUILD-MAX-HEAP()」用來建立「max-heap」、第二部分的「MAX-HEAPIFY()」為透過遞迴讓整棵二元樹形成「max-heap」的過程。

建立好「max-heap」之後，第三部分的「HEAP-SORT()」先將根與最末端節點的值對調，讓最大值跑到最尾端，排序好的尾部節點就從下一次的排序範圍中排除。新的排序範圍再跑一次「MAX-HEAPIFY()」，以維持「max-heap」，持續往前進行到第 0 個節點（即樹的「根」）都完成排序為止。

第一部分：BUILD-MAX-HEAP()

透過迴圈，讓每棵子樹都執行「MAX-HEAPIFY()」，使根的值為最大；第一棵處理的子樹其根在第「Math.floor(arr.length/2)」項，從此項以前的每個節點都是其他子樹的根，因此迴圈從第「Math.floor(arr.length/2)」項跑到第 0 項。

第二部分：MAX-HEAPIFY()

取任一子樹的根為第「i」項、左葉為第「l」項、右葉為第「r」項，第「l」項即為第「2‧i+1」項、第「r」項為第「2‧i+2」項。

先比較第「i」項與第「l」項的值，將較大者設為第「largest」項；再比較第「r」項與第「largest」項的值，將較大者設為第「largest」項；經過兩輪比較，即可以找到子樹中最大的值所在位置。

若最大的值不為第「i」項，則將第「i」項與第「largest」項的值調換，讓最大值跑到根；接著取第「largest」項為根，跟下層子樹比較，確保下層子樹的最大值也在根，透過不斷遞迴往下，最終可讓整棵樹的每棵子樹最大值都在根、形成「max-heap」。

第三部分：HEAP-SORT()

「max heap」的最大值在根，將根的值與最末端節點互換，最末端區域即完成排序，排除在下一輪排序之外，接著再從第 0 項開始執行「MAX-HEAPIFY()」，讓整棵樹維持「max heap」，以便執行下一輪的「HEAP-SORT()」。

由於堆積排序有多次調換過程，相同大小的值有可能無法維持原有順序，因此屬於「不穩定排序（unstable sort）」。

例如下圖中，原紅 6 在綠 6 之前，但經過調換後，紅 6 變成在綠 6 之後：

程式碼範例（JavaScript）

//第一部分
function buildMaxHeap(){
    for(i=Math.floor(arr.length/2); i>=0; i--){         //從最後一棵子樹往前運行maxHeapify()，待每棵子樹的最大值都在根後，即完成max-heap
        maxHeapify(i);
    }
}

//第二部分
function maxHeapify(i){
    let l = 2*i+1;                                      //以第i項為根的子樹左葉為第(2*i+1)項，設為第l項
    let r = 2*i+2;                                      //以第i項為根的子樹右葉為第(2*i+2)項，設為第r項

    //比較第l項與第i項的值
    if(l<=heapSize && arr[l]>arr[i]){                   //若最大值在第l項，則設largest第l項，否則largest為第i項
        largest = l;
    } else {
        largest = i;
    }

    //比較第r項與上一輪比較第largest項的值
    if(r<=heapSize && arr[r]>arr[largest]){             //若最大值在第r項，則設largest為第r項，否則largest維持在第i項
        largest = r;
    }

    if(largest != i){                                   //若第largest項不為第i項，則將第i項與第largest項的值調換，使最大值在根
        let temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        maxHeapify(largest);                            //第largest項透過遞迴向下比較，讓該層子樹以下的每棵子樹最大值都在根
    }
}

//第三部分
function heapSort(){
    buildMaxHeap();                                     //先讓樹變成max-heap才可進行堆積排序
        for(i=arr.length-1; i>=0; i--){                 //從最後一項開始與根的值調換，讓節點中的值從尾到頭由大而小排列
            let temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapSize -= 1;                              //每次調換完成後，將末端已排序的節點排除於下一輪排序之外
            maxHeapify(0);                              //從根開始往下執行maxHeapify()，讓整棵樹變回max-heap
        }
    return arr;                                         //待整棵樹都完成排序後，回傳排序好的陣列  
}

時間複雜度

以上述由大到小排列的過程為例，若共有 n 筆資料，可依序分析堆積排序三大步驟時間複雜度如下：

1. BUILD-MAX-HEAP()：維持「max-heap」結構，從第 Math.floor((arr.length/2)) 項開始一路到第 0 項都要跑過一次，時間複雜度為 O(n/2)=O(n)。
2. MAX-HEAPIFY()：建立「max-heap」過程，對於任一個值而言，在根與葉之間移動，最多移動 (log₂ n) 層，也就是移動 (log₂ n) 次，時間複雜度為 O(log₂ n)=O(log n)。
3. HEAP-SORT()：從最後一項到第一項每筆資料都會一一被切到陣列中，時間複雜度為 O(n)。

綜合以上三點，時間複雜度為 O(n)+O(n·log n)=O(n·log n)。

「MAX-HEAPIFY()」中，每筆資料最多移動 (log₂ n) 層的推斷方式如下：

空間複雜度

堆積排序為「原地演算法（in-place algorithm）」，所有的值都在原空間中調換，無需使用額外儲存空間輔助，因此空間複雜度為 O(1)。