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

heap sort 堆積排序 介紹與實作原理

堆積排序是透過最大堆積樹來進行排序，其實作與原理如下
主要核心是要讓 root 大於左右子樹，由於我們每次都能夠找出 root，且必定大於左右子樹，因此我們只需要將 root 提出來，再讓左右子樹中的最大值替補 root，依序遞迴擊可。

• 我們用一維陣列來表達我們的二元樹
• 其中 index 0 一定是二元樹中最大的數字
• 透過遞迴，參數： i
  • 以當前 i 節點為 root，L、R 分別是左右子樹
  • 如果左子樹數值比 i 數值還要大，那就讓 i 與左子樹交換
  • 如果右子樹數值比 i 數值還要大，那就讓 i 與右子樹交換
  • 如果先前有進行交換的動作，那我們就讓與 i 交換的子樹再重新進行遞迴

我們主要是維護二元堆積樹的 root 最大，如果 root 與其他數值有做交換，那我們必須讓 root 往下至其適合的位置，適合的位置：左右子樹都沒有比他還大，root 本身比左右子樹更大

時間複查度為 \(O(n log n)\)，在某些演算法中會用到堆積排序，因此算是篇重要的排序演算法之一。

參考來源

HeapSort by geeksforgeeks

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;
}

心得

由於 C++ 已經有很多 sort 套件了，因此我在高中學會後我就再也沒有去複習這些知識。

剛好現在上課有用到那就來複習，順便把它寫出邏輯八！

程式執行結果