iT邦幫忙

1

【小馬的資結演算法秘笈】(3)堆積排序法- heapSort

今天要來講另一種經典的排序方法,叫作堆積排序法(heapSort)
我們會用到一種叫作heap的資料結構,
heap這個單字中文翻譯叫作堆,
就是把東西放成一堆的感覺

heap是一個二元樹的結構,滿足兩個性質:

  • heap property: 每個父節點要比小孩節點還要小(滿足此特性為min heap,若父節點比小孩節點還要大則為 max heap)
  • shape property: 指heap的長相一定要由上到下、由左到右的擺放節點

譬如說底下是一個heap:
https://ithelp.ithome.com.tw/upload/images/20200314/20117114WwVEtAL5H3.png

與extract-min
這個結構可以幫助我們快速的做到兩件事,
insert: 在heap中插入一個元素
extract-min: 把heap中最小的元素拿走

insert- O(log n)的時間

要插入一個元素很簡單,譬如我們想在上面畫的那個heap裡插入「1」這個元素,
直接放到heap的下一個位置即可(這樣一定滿足shape property),如圖:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114qFxp9v8oKH.png

可是這樣的話你會發現好像不太對,
heap property說上面的點一定要比下面的點還要小,
可是現在位於上面的「8」比新加入的「1」還大,那怎麼辦呢?

解決的方法就是讓插入的元素跟它的父親節點比較,
如果插入的元素比較小,就跟它父親節點交換,
一直重複做直到大小關係是正確的,
如下圖演示:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114P7GhAy91bW.png
https://ithelp.ithome.com.tw/upload/images/20200314/20117114pblHgf39Yc.png

你會發現,交換的次數最多就是跟樹的高度相同,
所以若樹的節點個數為n個,交換的次數即是O(log n)這麼多次

extract-min- O(log n)的時間

要找到一個heap最小的元素很簡單,
一定是在最上面的位置,
不過如果我們直接把最小的那個元素拿走:
https://ithelp.ithome.com.tw/upload/images/20200314/20117114zXYdd3Myvq.png

然後你就會發現這形狀好像不太對,因為最上面少了一個節點,
所以我們需要把最後一個節點的元素直接補到最上面,
以維持heap的形狀:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114B2PO68TO79.png

但這時heap property又不滿足了,
其實接下來要做的事跟插入元素做的事很類似,
插入元素是把元素跟上面交換,
所以這次我們其實是要把「11」這個元素跟下面比較小的元素交換,
讓大小關係是正確的

https://ithelp.ithome.com.tw/upload/images/20200314/20117114N8t1qnSenC.png
(注意不能把11跟8交換,不然8會比6還大)

https://ithelp.ithome.com.tw/upload/images/20200314/20117114Xm5stvXUfq.png

這邊交換的次數最多也是跟樹的高度相同,
所以若樹的節點個數為n個,交換的次數亦是O(log n)這麼多次

程式如何存一個heap?

了解一個heap的結構之後,
我們接下來可以用程式將heap存下來了,
最簡單的方式應該是用陣列來存就可以了,
我們將heap由上而下、由左到右的順序給節點編號1,2,3,…,
就可以用一個陣列表示一個heap了

https://ithelp.ithome.com.tw/upload/images/20200314/20117114TQwZIikwpD.png

我們陣列0號的位置空下來,這樣可以方便計算出父節點跟小孩節點,
假設有一個節點的編號是「i」,則-

  • 父節點的編號是「i/2」(尾數捨去)
  • 小孩節點的編號分別是「2*i」與「2*i+1」

如何用heap幫助我們排序

如果我們有insert和extract-min兩個運算,
那麼要排序應該會不難了,
首先對於一個要排序的陣列(假設裡面有n個數),

  1. 先不斷的用insert函數把元素放到heap裡面 (共插入n個元素,每次要log n的時間)
  2. 在不斷用extract-min幫我們把元素從heap裡面拿出來 (共拿出n個元素,每次要log n的時間)

總時間為O(nlogn)

程式碼範例

這邊我們把Heap包裝為一個類別

#include <iostream>
#include <vector>
using namespace std;

class Heap {
private:
    vector<int> array = {0}; //初始給一個元素,讓index0的位置閒置
public:
    Heap() = default;
    Heap(vector<int> _array);
    void insert(int num);
    int extract_min();
    vector<int> HeapSort();
};

Heap::Heap(vector<int> _array) {
    for (int i = 0; i < _array.size(); i++) {
        insert(_array[i]);
    }
}

void Heap::insert(int num) {
    array.push_back(num);
    int idx = array.size()-1;
    while (idx / 2 > 0 and array[idx] < array[idx / 2]) {
        swap(array[idx], array[idx / 2]);
        idx /= 2;
    }
}

int Heap::extract_min() {
    int min_element = array[1];
    int sz = array.size()-1; //元素個數
    swap(array[1], array[sz]);
    int idx = 1;
    while (idx * 2 <sz) {
        int small_chlid_idx = idx * 2; //判斷小孩節點比較小的那個編號
        if (small_chlid_idx + 1 < sz && array[small_chlid_idx + 1] < array[small_chlid_idx])
            small_chlid_idx++; 
        if(array[idx] > array[small_chlid_idx])
            swap(array[idx], array[small_chlid_idx]);
        idx = small_chlid_idx;
    }
    array.erase(array.end()-1); //清掉最後一個元素(即最小的那個)
    return min_element;    
}

vector<int> Heap::HeapSort() {
    int sz = array.size() - 1; //元素個數
    vector<int> vec;
    for (int i = 0; i < sz; i++) {
        vec.push_back(extract_min());
    }
    return vec;
}

int main()
{
    vector<int> vec = { 1,5,6,3,2,8,10,7 };
    Heap heap(vec);
    vec = heap.HeapSort();
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << " " ;
    cout << endl;
    return 0;
}

尚未有邦友留言

立即登入留言