Python 堆佇列演算法

---

堆資料結構可以用來表示優先佇列。在 Python 中，它可以透過 heapq 模組使用。這裡它建立了一個最小堆。因此，當優先順序為 1 時，它表示最高優先順序。當插入新元素時，堆結構會更新。

要使用此模組，我們應該使用以下方法匯入它：

import heapq

有一些與堆相關的操作。它們是：

方法 heapq.heapify(iterable)

它用於將可迭代資料集轉換為堆資料結構。

方法 heapq.heappush(heap, element)

此方法用於將元素插入堆中。之後重新堆化整個堆結構。

方法 heapq.heappop(heap)

此方法用於返回並從堆頂刪除元素，並在其餘元素上執行堆化。

方法 heapq.heappushpop(heap, element)

此方法用於在一個語句中插入和彈出元素。

方法 heapq.heapreplace(heap, element)

此方法用於在一個語句中插入和彈出元素。它從堆的根部刪除元素，然後將元素插入堆中。

方法 heapq.nlargest(n, iterable, key=None)

此方法用於從堆中返回 n 個最大元素。

方法 heapq.nsmallest(n, iterable, key=None)

此方法用於從堆中返回 n 個最小元素。

示例程式碼

線上演示

import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)

輸出

[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
Popped Element: 7
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[89, 65, 58, 41]