mtmatt.Page

commonPage

0%

Binary Heap

發表於 分類於
文章字數： 3.9k 所需閱讀時間 ≈ 7 分鐘

Introduction

堆積是一種特殊的樹狀資料結構，滿足以下性質，以下用最大堆積為例

  1. Parent Node 的值總是大於等於 Child Nodes 的值。
  2. Binary Heap 為一個完全二元樹，即除了最底層，其他層都是滿的，且最底層的節點都靠左對齊。

至於什麼是二元樹？二元樹是一種樹狀結構，其每個節點最多只能有兩個 Children。

Heap operations

堆積有以下幾種操作

  1. Build Heap: 將一個陣列轉換成堆積
  2. Insert: 插入一個新元素到堆積中
  3. Extract Max: 移除並回傳堆積中最大的元素

Build Heap (Heapify)

將一個陣列轉換成堆積的方法稱為 Heapify。

常見的方法是從最後一個 Parent Node 開始，將每個 Parent Node 與其 Children 比較，若 Parent Node 小於 Children，則交換兩者的值，並繼續往下比較，直到該 Parent Node 大於等於所有他的新 Children。

Insert

插入一個新元素到堆積中的方法是將新元素插入到堆積的最後一個位置，然後將該元素與其 Parent Node 比較，若新元素大於 Parent Node，則交換兩者的值，並繼續往上比較，直到該新元素小於等於 Parent Node ，或是已經抵達根節點。

Extract Max

移除並回傳堆積中最大的元素的方法是將根節點與最後一個節點交換，然後移除最後一個節點，並將根節點與其 Children 比較，若根節點小於 Children 中的最大值，則將他與最大的 Child Node 交換，並繼續往下遞迴比較。

Implementation

接下來，我們將實作一個最大堆積，並完成上述的操作。

  1. heapify: 將一個陣列轉換成堆積
  2. push(insert): 插入一個新元素到堆積中
  3. top + pop(extract max): 移除並回傳堆積中最大的元素

閱讀完陣列內容後，程式會執行以下操作，操作前會先調用 heapify 將陣列轉換成堆積。

  1. 1 <val>: 在堆積中插入一個新元素 <val>
  2. 2: 移除並回傳堆積中最大的元素

Template

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
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>

namespace {

inline int left_child(int node) {
    return (node << 1) | 1;
}

inline int right_child(int node) {
    return (node << 1) + 2;
}

inline int parent(int node) {
    return (node - 1) >> 1;
}

class Heap {
public:
    Heap(const std::vector<int> &elements) : values(elements) {
        heapify();
    }
    void heapify();
    void push(int val);
    int pop_top();
private:
    std::vector<int> values;    
};

void Heap::heapify() {
    // Your code below

    // Your code above
}

void Heap::push(int val) {
    // Your code below

    // Your code above
}

int Heap::pop_top() {
    int top_element{0};
    // Your code below

    // Your code above
    return top_element;
}

}

const int PUSH{1};
const int POP{2};

const int MAX_PILES{100010};

int main(void) {
    std::ios::sync_with_stdio(0);std::cin.tie(0);

    int n;
    std::cin >> n;
    std::vector<int> elements(n);
    for (auto &i : elements) {
        std::cin >> i;
    }

    Heap heap(elements);

    int m;
    std::cin >> m;
    for (int i{0}; i < m; ++i) {
        int op, value;
        std::cin >> op;
        switch (op) {
        case PUSH:
            std::cin >> value;
            heap.push(value);
            break;
        case POP:
            std::cout << heap.pop_top() << "\n";
            break;
        }
    }
}

Input

輸入的第一行為一個整數 n，代表接下來陣列中有 n 個元素。

接下來的一行為 n 個整數，代表陣列的元素。

接下來的一行為一個整數 q，代表接下來有 q 個操作。

接下來的 q 行為操作，操作有兩種，分別為 1 <val> 和 2。

Output

對於每個操作 2，輸出一行，為堆積中最大的元素。如果堆積為空，則輸出 -1。

Sample Input

1
2
3
4
5
6
7
8
5
1 2 3 4 5
5
2
1 6
2
2
2

Sample Output

1
2
3
4
5
6
4
3

Constraints

  • (1 \leq n \leq 10^5)
  • (1 \leq q \leq 2 \times 10^5)
  • (-10^9 \leq \text{val} \leq 10^9)

Application

Median Maintenance

Median Maintenance 是一個維護中位數的問題，即對於一個數列，每次插入一個新元素後，求該數列的中位數。

一個簡單的方法是每次都將數列排序後，取中間的元素，但這樣的時間複雜度為 (O(n \times n \log n))。

我們可以使用兩個堆積來解決這個問題，一個最大堆積 max_heap 用來存放數列的一半，一個最小堆積 min_heap 用來存放數列的另一半。由於特殊的存放的方式，我們可以保證當數列的元素個數為奇數時，中位數為 max_heap 的根節點，當數列的元素個數為偶數時，中位數為 max_heap 的根節點和 min_heap 的根節點的平均值。

每次插入一個新元素時，我們先將該元素插入 max_heap，然後將 max_heap 的最大元素取出插入 min_heap，並保持 max_heap 的元素個數大於等於 min_heap 的元素個數。

這樣的時間複雜度為 (O(n \log n))。另一種方法是使用紅黑樹等平衡樹，時間複雜度同為 (O(n \log n)) 但常數較大。

如果一個數列有基數個數字，中位數表示排序後最中間的。如果是偶數個數字，則表示中間兩個的平均，在這一題，你只需要用整數除法即可。

Dijkstra’s Shortest Path Algorithm

Dijkstra’s Shortest Path Algorithm 是一個用來求單源最短路徑的演算法，其基本思想是每次選擇當前距離最短的節點，並更新與其相鄰的節點的距離。我們可以使用一個最小堆積來實現 Dijkstra’s Shortest Path Algorithm，每次從堆積中取出距離最短的節點，並更新與其相鄰的節點的距離。複雜度為 (O((V + E) \log V))。

Huffman Coding

Huffman Coding 是一種用來將一個字串編碼的演算法，其基本思想是將出現頻率較高的字元編碼為較短的編碼，出現頻率較低的字元編碼為較長的編碼。我們可以使用一個最小堆積來實現 Huffman Coding，每次從堆積中取出出現頻率最低的兩個字元，並將他們合併成一個新的節點，然後將新的節點插入堆積中。