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]