堆積排序(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)。

#演算法 #堆積排序







你可能感興趣的文章

Day 69

Day 69

Custom Hook 來自己寫一個  hook 吧!

Custom Hook 來自己寫一個 hook 吧!

儲存空間使用相關指令

儲存空間使用相關指令






留言討論