HackMDPython 及 C++ 優先佇列 (priority queue)
作者：王一哲
日期：2023年12月31日
前言
優先佇列 (priority queue) 又稱為堆積佇列 (heap queue)，Python 及 C++ 都有對應的容器，不過 Python 會將最小值放在佇列最上面，而 C++ 預設則是將最大值放在佇列最上面。以下的程式碼測試版本為 Python 3.10.12 及 C++14。
Python 語法
如果要在 Python 中使用優先佇列，需要引入函式庫 heapq；如果是在 LeetCode 網站上解題，因為網站已經引入了 heapq，不需要自己引入 heapq。語法為
import heapq import *
由於 Python heapq 的特性，使用時可以將它視為串列，初始化一個 heap 時，語法通常為
h = []
將資料放入 heap
語法為
heapq.heappush(heap, 資料)
例如以下的程式碼
h = []
heapq.heappush(h, 3) # h 的內容為 [3]
heapq.heappush(h, 1) # h 的內容為 [1, 3]
heapq.heappush(h, 2) # h 的內容為 [1, 3, 2]
從 heap 中取出並回傳最小的資料
語法為
heapq.heappop(heap)
如果 heap 是空的則會回傳錯誤訊息 IndexError。例如以下的程式碼，若 h 的內容為 [1, 3, 2]，則
n = heapq.heappop(h) # 回傳1，h 的內容變為 [2, 3]
n = heapq.heappop(h) # 回傳2，h 的內容變為 [3]
n = heapq.heappop(h) # 回傳3，h 已經是空的
n = heapq.heappop(h) # 回傳錯誤訊息 IndexError
將資料放入 heap 再取出並回傳最小的資料
語法為
heapq.heappushpop(heap, 資料)
效果相當於先呼叫 heappush 再呼叫 heappop，但是執行效率比較好。例如以下的程式碼，若 h 的內容為 [1, 3, 2]，則
n = heapq.heappushpop(h, 4) # 回傳1，h 的內容變為 [2, 3, 4]
從 heap 中取出並回傳最小的資料再將另一筆資料放入 heap
語法為
heapq.heapreplace(heap, 資料)
效果相當於先呼叫 heappop 再呼叫 heappush，但是執行效率比較好。如果 heap 是空的會回傳錯誤訊息 IndexError。例如以下的程式碼，若 h 的內容為 [1, 3, 2]，則
n = heapq.heapreplace(h, 0) # 回傳1，h 的內容變為 [0, 3, 2]
將串列轉為 heap
語法為
heapq.heapify(串列名稱)
例如以下的程式碼
x = [5, 1, 4, 2, 3]
heapq.heapify(x) # x 變為 [1, 2, 4, 5, 3]
合併多個已排序的串列為一個 heap
語法為
heapq.merge(串列1, 串列2, ..., key=None, reverse=False)
輸入的串列可以有好幾個。key 參數是比較依據，預設值為 None，直接比較資料本身。reverse 預設值為 Fasle、由小到大排序，輸入的串列也要由小到大排序。要做到同樣的效果，也可以使用 sorted 及 itertools.chain，例如以下的程式碼
import itertools
a = [1, 3, 5, 7, 9]
b = [2, 4, 6, 8, 10]
c = list(heapq.merge(a, b))
d = sorted(itertools.chain(a, b))
# c, d 皆為 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
reverse 也可以改成 True、由大到小排序，輸入的串列也要由大到小排序。要做到同樣的效果，也可以使用 sorted 及 itertools.chain，例如以下的程式碼
import itertools
a = [9, 7, 5, 3, 1]
b = [10, 8, 6, 4, 2]
c = list(heapq.merge(a, b, reverse=True))
d = sorted(itertools.chain(a, b), reverse=True)
# c, d 皆為 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
回傳一個串列中前 n 個最大值
語法為
heapq.nlargest(n, 串列, key=None)
key 參數是比較依據，預設值為 None。例如以下的程式碼
a = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
n = heapq.nlargest(5, a) # 回傳值為 [10, 9, 8, 7, 6]
回傳一個串列中前 n 個最小值
語法為
heapq.nsmallest(n, 串列, key=None)
key 參數是比較依據，預設值為 None。例如以下的程式碼
a = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
n = heapq.nsmallest(5, a) # 回傳值為 [1, 2, 3, 4, 5]
C++ 語法
如果要在 C++ 中使用優先佇列，需要引入函式庫 queue，語法為
#include <quque>
産生優先佇列 priority_queue 時，通常會從一個已經存在的一維 array 或 vector 輸入資料，預設的排序方式為由大到小，如果要改成由小到大則需要再加上 functional 函式庫中的 greater，例如以下的程式碼
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
int a[] = {5, 1, 4, 2, 3};
vector<int> v (a, a+5);
priority_queue<int> b; // 空的
priority_queue<int> c (a, a+5); // 內容為 {5, 4, 3, 2, 1}
priority_queue<int> d (v.begin(), v.end()); // 內容為 {5, 4, 3, 2, 1}
priority_queue<int, vector<int>, greater<int>> e (a, a+5); // 內容為 {1, 2, 3, 4, 5}
return 0;
}
檢查 priority_queue 是否是空的
語法為
名稱.empty();
如果是空的回傳1，如果不是空的回傳0。例如以下的程式碼，假設 b 是空的，c 的內容為 {5, 4, 3, 2, 1}，則
cout << b.empty() << "\n"; // 印出1
cout << c.empty() << "\n"; // 印出0
回傳 priority_queue 的長度
語法為
名稱.size();
例如以下的程式碼，假設 b 是空的，c 的內容為 {5, 4, 3, 2, 1}，則
cout << b.size() << "\n"; // 印出0
cout << c.size() << "\n"; // 印出5
回傳 priority_queue 最上面的資料
語法為
名稱.top();
例如以下的程式碼，假設 c 的內容為 {5, 4, 3, 2, 1}，則
cout << c.top() << "\n"; // 印出5
將資料加入 priority_queue
有兩種工具，語法為
名稱.push(資料);
名稱.emplace(資料);
例如以下的程式碼，假設 c 的內容為 {5, 4, 3, 2, 1}，則
c.push(0); // 內容為 {5, 4, 3, 2, 1, 0}
c.emplace(-1); // 內容為 {5, 4, 3, 2, 1, 0, -1}
移除 priority_queue 最上方的資料
語法為
名稱.pop();
例如以下的程式碼，假設 c 的內容為 {5, 4, 3, 2, 1}，則
c.pop(); // 內容變為 {4, 3, 2, 1}
交換兩個 priority_queue 的資料
語法為
名稱1.swap(名稱2);
例如以下的程式碼，假設 c 的內容為 {9, 7, 5, 3, 1}，d 的內容為 {8, 6, 4, 2}，則
c.swap(d); // c, d 互換資料
常用技巧：依序印出 priority_queue 所有的資料
假設 c 的內容為 {9, 7, 5, 3, 1}，用以下的程式碼可以依序印出 c 所有的資料
while(!c.empty()) {
cout << c.top() << "\n";
c.pop();
}
結語
某些題目只要求將最大或最小的資料排在佇列最上方，其它資料不需要排序，這時使用優先佇列儲存資料特別方便。以上只是我目前會用到的功能，如果以後有遇到其它用法會再補充。
