【C++】競程筆記（資料結構：Heap）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

簡介

Heap（堆積），是一個完全二元樹的資料結構，主要應用於優先佇列（priority queue）中。

由於他是完全二元樹結構，所以：

• 除了最底層外，其他每一層都是滿的。
• 最底層節點從左到右依序填滿。

樹上的每一個節點儲存一個可以比較大小的鍵值（key），並支援以下操作：

• 插入一個鍵值
• 詢問目前最大的鍵值
• 刪除最大的鍵值
  From NTUCPC Guide

Heap 通常遵守下列其中一種堆積性質：

1. 最小堆（Min-Heap）：每個節點的值都 $\leq$ 其子節點的值。（根節點是整棵樹中最小的元素）
2. 最大堆（Max-Heap）：每個節點的值都 $\ge$ 其子節點的值。（根節點是整棵樹中最大的元素）

Image Source：https://www.geeksforgeeks.org/dsa/heap-data-structure/

以下網站有可以滑動的視窗，展示哪一種是 invalid heap，哪一種是 valid heap。

https://www.geeksforgeeks.org/dsa/heap-data-structure/

Binary Heap 實作方式

大致上兩種：

1. 樹狀結構（不常見）
2. 陣列形式（常用）

（預設根節點的 index = 0）若某節點在索引 i：

• 左子節點在 2i + 1
• 右子節點在 2i + 2
• 父節點在 (i - 1) / 2

在此使用 vector 實作（最小堆）：

1. int getMin()

代表回傳堆疊根節點的值（也就是最小值），複雜度 $O(1)$ 。

// From NTUCPC Guide
int getMin(vector<int> &heap) {
    if (heap.empty())
        printf("empty!\n");
    else return heap[1];
}

1. void insert(int x)

要加入一個值為 $x$ 的數字進去 Heap 裡面。作法就是先將 $x$ 先丟進去最下面，然後一直往上，只要發現 $x$ 現在的節點比其父節點的值小，就交換他們兩個，並繼續看。

// From NTUCPC Guide
// Comment by LukeTseng
void Insert(vector<int> &heap, int x) {
    heap.push_back(x); // 推到新葉節點
    int last = heap.size() - 1; // last 為新插入節點的索引，用來向上檢查
    while (last > 1){ // 跳過索引 0 和根節點（1），因為根節點沒有父節點可比較
        if (heap[last] < heap[last / 2]) // 若子節點比較小，就交換（最小堆實作）
            swap(heap[last], heap[last / 2]);
        last /= 2;
    }
}

1. void deleteRoot(int x)

刪除根節點。將根換成最後的節點（最後的節點也刪掉），然後開始遞迴往下：如果目前的值比左右子樹的最小值大，則與左右子樹的最小值交換，並且往那個子樹遞迴下去。

// From NTUCPC Guide
// Comment by LukeTseng
void deleteRoot(vector<int> &heap) {
    swap(heap[1], heap[heap.size() - 1]); // 根節點的 index 為 1，跟最後一個節點交換
    heap.pop_back(); // 移除最後一個節點（會破壞最小堆性質，所以接下來要重建）
    int pos = 1; // 從 index = 1 開始向下檢查
    while (pos < heap.size()) {
        int l = 2 * pos, r = 2 * pos + 1; // 取左右子節點的索引
        // 左：2*i，右：2*i+1
        if (l >= heap.size()) break; // 若左子節點不存在（也代表右子節點不會存在），則是葉節點，不用繼續下去
        int min_child = r; // 決定較小子節點
        // 若右子節點不存在，或左子節點小於右子節點，則選左邊為 min_child
        // 這邊是為了找到「兩個子節點中較小的那一個」，以便和 heap[pos] 比較。
        if (r >= heap.size() || heap[l] < heap[r])
            min_child = l;
        // 若子節點比目前節點還小，代表違反 Min-Heap 規則
        if (heap[min_child] < heap[pos]) {
            swap(heap[pos], heap[min_child]); // 交換
            pos = min_child;
        }
        else break; // 若符合規則（父節點 <= 子節點），就跳出迴圈。
    }
}

insert()、deleteRoot() 時間複雜度均為 $O(logn)$ 。

STL in Heap

使用前先引入標頭檔 <queue>。

語法：

priority_queue<T, c, comp> pq;

T：優先佇列的型態。

pq：優先佇列名稱。

c：底層容器。預設使用 vector。

comp：比較函數。

priority_queue 為最大堆（max-heap）容器配接器，預設會將最大值放在頂端，若要將最小值放到頂端，則將 comp 改為 greater<int>，如下所示：

priority_queue<int, vector<int>, greater<int>> minHeap;

常見操作

• push()：將資料丟入堆積內部
• pop()：移除堆積頂端元素。
• top()：回傳堆積頂部元素（不刪除）。
• size()：回傳堆積元素數量。
• empty()：檢查堆積是否為空。

小範例：

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

int main() {
    priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    while (!pq.empty()) {
        cout << pq.top() << " "; // 取得頂端元素
        pq.pop(); // 移除頂端元素
    }
    return 0;
}

Output：

20 10 5

習題練習

排隊買飲料

Source：https://tioj.ck.tp.edu.tw/problems/1999

限制條件：

• 每個店員一次只能服務一名顧客。
• 店員必須按照順序接客。
• 每位顧客所點飲料表示服務時間。
• 每個店員的處理時間皆相同（1 min / 杯）。

解題思路：

1. 用最小堆處理店員的「忙碌時間結束點」。
2. 每位店員的初始可用時間 = 0。
3. 按照排隊順序，依序將每位顧客交給「目前最早可用的店員」：
   • 完成時間 = 店員目前可用時間 + 顧客需要的時間
   • 將店員的可用時間更新為該完成時間，並放回堆中。

最後輸出 max_time。

19 行中的 min(M, N) 是為了考慮效能，如果直接寫 M 會造成效能浪費，舉例：

假設 M = 10000，N = 5。

然而你卻最多只用到 5 個店員，9995個店員沒用到，不就造成效能浪費嗎？

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    vector <int> d(N); // 飲料數（所需時間）
    
    for (int i = 0; i < N; ++i){
        cin >> d[i];
    }
    
    priority_queue <int, vector<int>, greater<int>> e; // 員工可用時間
    
    for (int i = 0; i < min(M, N); ++i){ // min(M, N) 考慮效能
        e.push(0);
    }
    
    int max_time = 0;
    
    for (int i = 0; i < N; ++i){
        int available_time = e.top(); // 可用時間
        e.pop();
        
        int finish_time = available_time + d[i]; // 完成時間
        max_time = max(max_time, finish_time);
        
        e.push(finish_time);
    }
    
    cout << max_time;
    
    return 0;
}