堆積排序(Heap Sort)

在提到堆積排序前我們先講講樹的資料結構，因為在堆積排序中會使用到某一種樹。

樹-資料結構

那樹是甚麼

抽象資料類型
被用來模擬分層資料結構
無循環graph

在樹當中只會有一個root value，也就是樹根，看到下面那張圖7,5,6,9都有Subtree(子樹)，每個圈圈我們稱它為node(節點)，箭頭稱為edge，以圖片藍色圈起來的子樹為例，7就是2, 10, 6的parent node，而2, 10, 6就是7的children node。

二元樹(Binary Tree)

在樹的資料結構中有許多不同的樹，最常見的樹為二元樹。

二元樹中也有不同種類

(Types of Binary Tree || Designed by Anand K Parmar)

1. Full Binary Tree

Full Binary Tree 每個節點都有 0 或 2 個子節點

2. Complete Binary Tree

Complete Binary Tree 除了最後一層外，所有層節點都是滿的，在最後一層中，節點盡可能位於左側

3. Degenerate(or Pathological) Binary Tree

Degenerate(or Pathological) Binary Tree 每個父節點只會有一個子節點

4. Perfect Binary Tree

Perfect Binary Tree 內部節點都有兩個子節點，並且左右都處於相同深度

5. Balanced Binary Tree

Balanced Binary Tree 每個節點的左右子樹的高度最多相差1的二元樹

Max Heap

max heap 就是這次排序中會使用到的資料結構

是一個 Complete Binary Tree
SubTree 的 root 一定會是最大

(圖片來自Binary heap)

堆積排序介紹

先將數組轉換成Complete Binary Tree資料結構，再換成Max Heap，這時root值將會是最大值，將root值移出去，再繼續將樹轉換成Max Heap，依此類推，這就是堆積排序。

(圖片來源)

虛擬碼

首先是建立Max Heap 的pseudo code

heapSize 和 arr 為全域變數，因為在多個function中使用

虛擬碼中，heapSize 的值為數組 arr 的長度减 1。然後，有一個迴圈從 heapSize / 2 開始，遍歷所有的非葉子節點，至第 0 個節點。

每個非葉子節點會被傳遞給 MAX-HEAPIFY 函數。MAX-HEAPIFY 函數的作用是使其成為max heap，使得父節點的鍵值都大於等於其子節點的鍵值。

經過這段虛擬碼的執行後，數組 arr 會被轉化成一個max heap。

BUILD-MAX-HEAP():
    heapSize = arr.length - 1
    for i from (heapSize / 2) to 0:
        arr = MAX-HEAPIFY(i)

這個虛擬碼做的事是在給定的節點i的子樹中，找到最大的節點並使之成為i的父節點。

最多走 $log2^n$層，這邊的n為node數量，假設有1024個node代表樹為10層

以下是該虛擬碼的詳細說明：

2，3行計算i節點的左右子節點在陣列中的位置。
4，5行
如果左子節點存在且大於根節點，那麼將左子節點設為最大值。
8，9行。
如果右子節點存在且大於當前的最大值，那麼將右子節點設為最大值。
10~12行。如果最大值不是根節點，則交換根節點和最大值並遞迴調用MAX-HEAPIFY(largest)保持max heap的性質。

這個 MAX-HEAPIFY 作用是將某一個節點下面的子樹調整成最大堆，並且讓根節點是最大值。

// BigO O(logn)
MAX-HEAPIFY(i):
    l = 2 * i + 1
    r = 2 * i + 2
    if l <= heapSize and arr[l] > arr[i]:	
        largest = l
    else:
        largest = i
    if r <= heapSize and arr[r] > arr[largest]:	
        largest = r
    if largest is not i:	
        swap arr[i] with arr[largest]	
        MAX-HEAPIFY(largest)

我們舉例arr = [8, 6, 2, 4, 5, 3, 7]，heapSize 就會等於 6，接著下來跑迴圈先給予i=3但arr[3]底下沒有節點，所以舉i=2為例子，丟進MAX-HEAPIFY，接下來往下看

假設i 為 2，這時候 l = 5, r = 6，將虛擬碼帶入數字

這邊可以看到找到最大值的index等於6，所以我們跟i位置的值交換位置，那他會從largest的位置再往下查看是否為最大值，如果不是就會再持續交換

再來才是本篇重點Heap sort的pseudo code，一開始創建max heap後將最大值與陣列最後一個值互換，這樣就能確保最後一個值為最大值，依照此步驟，依此類推，就可以完成陣列的排序。

HEAP-SORT():
    BUILD-MAX-HEAP(arr)
    for i from arr.length - 1 to 0:
        exchangeArr[0] with arr[i]
        heapSize = heapSize - 1
        MAX-HEAPIFY(0)

如下圖步驟循環

將資料建立成一個max heap。
將根節點(root)與最後一個節點交換，並將最後一個節點刪除。
重新調整heap，使其成為一個max heap。
重複步驟 2 和 3，直到heap中只剩下一個節點。

複雜度

時間複雜度為

$O(n log n)$

空間複雜度為

$O(1)$

`Heap Sort`程式碼

class HeapSort{
    constructor(arr){
        this.arr = arr;
        this.heapSize = arr.length;
    }

    buildMaxHeap(){
        this.heapSize = this.heapSize - 1;
        for(let i = Math.floor(this.heapSize/2); i >= 0; i--){
            this.maxHeapify(i);
        }
    }

    maxHeapify(i){
        let left = 2*i + 1;
        let right = 2*i + 2;
        let largest;

        if(left <= this.heapSize && this.arr[left] > this.arr[i]){
            largest = left;
        } else {
            largest = i;
        }

        if(right <= this.heapSize && this.arr[right] > this.arr[largest]){
            largest = right;
        }

        if(largest != i){
            let temp = this.arr[i];
            this.arr[i] = this.arr[largest];
            this.arr[largest] = temp;
            this.maxHeapify(largest);
        }
    }

    sort(){
        this.buildMaxHeap();
        for(let i = this.arr.length-1; i >= 0; i--){
            let temp = this.arr[0];
            this.arr[0] = this.arr[i];
            this.arr[i] = temp;
            this.heapSize--;
            this.maxHeapify(0);
        }
    }
}

let arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
let heap = new HeapSort(arr);
heap.sort();

console.log(heap.arr); // [1, 2,  3,  4,  7, 8, 9, 10, 14, 16]

LeetCode實戰

912. Sort an Array

給你一個整數陣列nums，請將陣列以升序排列並返回。您必須在O(nlog(n))時間複雜度內解決此問題，並使用較小的空間複雜度。

☑解法詳解

code:tada:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    let heapSize;

    function maxHeapify(i){
        let left = 2*i + 1;
        let right = 2*i + 2;
        let largest;

        if(left <= heapSize && nums[left] > nums[i]){
            largest = left;
        } else {
            largest = i;
        }

        if(right <= heapSize && nums[right] > nums[largest]){
            largest = right;
        }

        if(largest != i){
            let temp = nums[i];
            nums[i] = nums[largest];
            nums[largest] = temp;
            maxHeapify(largest);
        }
    }

    function buildMaxHeap(){
        heapSize = nums.length - 1;
        for(let i = Math.floor(heapSize/2); i >= 0; i--){
            maxHeapify(i);
        }
    }

    buildMaxHeap();
    for(let i = nums.length-1; i >= 0; i--){
        let temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        heapSize--;
        maxHeapify(0);
    }
    return nums
};