前言

Heap Sort 是利用 Min/Max Heap的特性，提取目前數列的最大值或最小值，最後形成排序好的數列，屬於 unstable sorting

關於 Heap 是什麼，在這篇有大概的解說，還有附上修課記錄的 pseudo code

Heap Sort

利用 Max-Heap的 ExtractMax，可以做 sorting
輸入數列建立Heap，每次把最大的提取出來 push到 array 裡，就是由大到小的 array
反過來如果是想要由小到大，則用 Min-Heap 來實作

這邊示範由小到大的排序

Min-Heap

先將數列排列成 Min-Heap的 形式，用 Insert 或是 BuildHeap 都可以
接著將 Min-Heap 做 ExtractMin

pseudo code

1
2
3
HeapSort(Heap[1..n])
    for i from 1 to n
        Heap[i] ← ExtractMin(H)

改變排序方式有一種更簡單的方式就是直接讓i變成後面開始放，這樣sorted array就是由大到小

這邊我用額外的空間紀錄排序好的數列，若有節省空間的需要可以再傳一個int size在ExtractMin的時候控制size即可

Code

以下附上完整的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int LeftChild(int index) {
    return index * 2 + 1;
}
int RightChild(int index) {
    return index * 2 + 2;
}
void SiftDown(int index, vector<int> &H) {
    int minIndex = index;
    int l = LeftChild(index);
    int r = RightChild(index);
    // choose smaller child to swap
    if(l < H.size() && H[l] < H[minIndex])
        minIndex = l;
    if(r < H.size() && H[r] < H[minIndex])
        minIndex = r;

    if(index != minIndex) {
        swap(H[minIndex], H[index]);
        SiftDown(minIndex, H); // recursive
    }
}
int ExtractMin(vector<int> &H) {
    int result = H[0];
    swap(H[0], H[H.size()-1]);
    H.pop_back();  // 釋放最後一個
    SiftDown(0, H);
    return result;
}
void BuildMinHeap(vector<int> &H) {
    int n = H.size();
    for(int i = n/2; i >= 0; i--) {
        SiftDown(i, H);
    }
}

vector<int> HeapSort(vector<int> &H) {
    vector<int> sorted;
    int n = H.size();
    for(int i = 0; i < n; i++) {
        sorted.push_back(ExtractMin(H));
    }
    return sorted;
}
int main() {
    cout << "heap, pls input array" << endl;
    vector<int> array;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        array.push_back(input);
    }
    BuildMinHeap(array);

    // print the heap
    for(int i = 0; i < array.size(); i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    vector<int> sorted = HeapSort(array);

    // print the heap
    for(int i = 0; i < sorted.size(); i++) {
        cout << sorted[i] << " ";
    }

    return 0;
}

複雜度

時間複雜度

Sequence Complexity
Random $O(NlogN)$
Nearly Sorted $O(NlogN)$
Reversed $O(NlogN)$
Few Unique $O(NlogN)$

Heap sort 的時間複雜度在所有情況下都是 $O(NlogN)$，獨立於資料的組成

空間複雜度

沒有用到額外的 array，$O(1)$ space

可以到 Toptal 的這個網頁觀看不同 case 的視覺化排序過程