Python 及 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

由於 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();
}

結語

某些題目只要求將最大或最小的資料排在佇列最上方，其它資料不需要排序，這時使用優先佇列儲存資料特別方便。以上只是我目前會用到的功能，如果以後有遇到其它用法會再補充。

參考資料

1. heapq --- 堆積佇列 (heap queue) 演算法
2. cplusplus.com std::priority_queue

---

HackMD 版本連結：https://hackmd.io/@yizhewang/S1EBLEAvT