演算法知識 - heap sort 堆積排序

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int num[] = {4,96,1546,13,48,34,77,48,31}; 
int num_size; //陣列的 size

void output(){ //輸出結果
    for(int i = 0 ; i < num_size ; i++)
        cout << num[i] << ' ' ;
    cout << '\n' ;
}

void heapify(int n, int i){ //建構、調整堆積樹，i 表示數值、n 表示樹的 size
    int root = i; //root 
    int L = 2 * i; //subtree
    int R = 2 * i + 1; //subtree

    //注意：以下只有交換 index
    if(L < n && num[L] > num[root]) root = L; //如果 root 比左子樹小就交換
    if(R < n && num[R] > num[root]) root = R; //如果 root 比右子樹小就交換

    //如果 root 已經被交換
    if(root != i){
        swap(num[root], num[i]); //這邊才真正進行交換
        heapify(n, root); //繼續遞迴，讓 i 可以到達完整的最大堆積樹，也就是當 i 為 root，左、右子樹都比 root 小。
    }
}

void heap_sort(){ //進行 heap_sort 排序
    //將每個數值放到適合的堆積位置
    //注意：i 是從 num_size/2 開始，因為我們是從最下層的子樹(root、L、R) 不斷做 heapify
    //到第一層的子樹，這樣才可以將之前堆積的狀態延續至上層。
    //如果從第一層開始做，那每一個 root 都只會是 L、R 的最大值，
    //但上層的 root 並不一定會大於下層或下下層的 root，這整棵樹就並不是一個完整堆積樹
    for(int i = num_size/2; i >= 0; i--) heapify(num_size, i);

    //不斷地拿出 root(最大數值)，放到數列最後面。
    for(int i = num_size-1; i >= 0; i--){
        swap(num[0], num[i]); //與數列中的最後一個數值交換。這樣越大的數值會被放到越後面
        heapify(i, 0); //由於 root 已經不再是最大，因此再次進行 heapify
        //注意：如果我們已經將 1 次 root 與數列最後一個數值交換，那我們下次就不可以把數列中的最後一個數值放入 heapify，不然這次做的堆積樹又會變成下次堆積樹 root，因此我們要將 num_size 減少。
        //因此這裡的 i 為未確定排序陣列的大小。
    }
}

int main()
{
    num_size = sizeof(num) / sizeof(num[0]); //紀錄陣列 size
    heap_sort();
    output();
    return 0;
}