# 堆積佇列 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 官方介紹