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

#include <iostream>
#include <vector>
#include <functional>

// Heap sort
// Time complexity: O(nlon(n)), Space complexity: O(1)
// 想法: 順序是從樹的底部(子問題)到頂，確保底部是正確的，遇到要更動的再往下更動，能確保性質是完整的
//       變成heap之後，最頂部是正確答案，與底部交換，存在底部的到最頂，再Heapify最頂一次，找下一個
// 注意: cmp(a,b) if a ? b return true，因為答案存在最後面，大小會反轉
void heapify(std::vector<int> &vec, int start, int end, std::function<bool(int, int)> cmp)
{
    int dad = start, son = start*2 + 1;
    while(son <= end){
        // select the greatest son, reverse the cmp
        if(son+1 <= end && !cmp(vec[son+1], vec[son]))
            ++son;
        // check
        if(!cmp(vec[dad], vec[son])){
            return;
        }
        else{
            std::swap(vec[dad], vec[son]);
            dad = son;
            son = dad*2+1;
        }
    }
}
void heap_sort(std::vector<int> &vec, std::function<bool(int, int)> cmp)
{
    // make it to heap
    for(int i = vec.size()/2 - 1; i >= 0; --i){
        heapify(vec, i, vec.size()-1, cmp);
    }
    // store the sorted number from bottom up
    for(int i = vec.size()-1; i >= 0; --i){
        std::swap(vec[i], vec[0]);
        heapify(vec, 0, i-1, cmp);
    }
}
int main()
{
    std::vector<int> vec = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    heap_sort(vec, [](int a, int b){ return a < b; });

    for(const auto &v : vec){
        std::cout << v << "\n";
    }
}