【C++】競程筆記（資料結構：Heap）
===
[TOC]
程式碼範例參考：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)$ 。
```cpp=
// From NTUCPC Guide
int getMin(vector<int> &heap) {
if (heap.empty())
printf("empty!\n");
else return heap[1];
}
```
2. void insert(int x)
> 要加入一個值為 $x$ 的數字進去 Heap 裡面。作法就是先將 $x$ 先丟進去最下面，然後一直往上，只要發現 $x$ 現在的節點比其父節點的值小，就交換他們兩個，並繼續看。
```cpp=
// 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;
}
}
```
3. void deleteRoot(int x)
> 刪除根節點。將根換成最後的節點（最後的節點也刪掉），然後開始遞迴往下：如果目前的值比左右子樹的最小值大，則與左右子樹的最小值交換，並且往那個子樹遞迴下去。
```cpp=
// 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>`，如下所示：
```cpp
priority_queue<int, vector<int>, greater<int>> minHeap;
```
### 常見操作
- push()：將資料丟入堆積內部
- pop()：移除堆積頂端元素。
- top()：回傳堆積頂部元素（不刪除）。
- size()：回傳堆積元素數量。
- empty()：檢查堆積是否為空。
小範例：
```cpp=
#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個店員沒用到，不就造成效能浪費嗎？
```cpp=
#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;
}
```
Sign in with Wallet
Connect another wallet