堆積佇列heap queue

今天來介紹Python Library 的Heap Queue

Heap(堆積)是一個Binary Tree(二元樹)，所以heap[0]是整個結構最小的元素

初始化 HeapQueue

給變數宣告成陣列即可

1
2

import heapq
h = []

Push

heapq.heappush(heap, item)

把 item 放進 heap，並保持 heap 性質不變。

1
2
3
4
5
6
7
8

import heapq
h = []
heappush(h, (5, 'write code'))
heappush(h, (7, 'release product'))
heappush(h, (1, 'write spec'))
heappush(h, (3, 'create tests'))
print(heappop(h))
# (1, 'write spec')

Pop

heapq.heappop(heap) 從 heap 取出並回傳最小的元素，同時保持 heap 性質不變。

如果 heap 是空的會產生 IndexError 錯誤。只存取最小元素但不取出可以使用 heap[0] 。

PushPop

heapq.heappushpop(heap, item)

將 item 放入 heap ，接著從 heap 取出並回傳最小的元素。

這個組合函式比呼叫 heappush() 之後呼叫 heappop() 更有效率。

Heapify

heapq.heapify(x)

在線性時間內將 list x 轉為 heap，且過程不會申請額外記憶體。

Merge

heapq.merge(*iterables, key=None, reverse=False)

可以給定多個可迭代物件(List等)合併出根據Key(比較依據function)的Heap Queue 。

參考資料

Python Heap Queue官方介紹