heapq 【堆積佇列】
簡介
What is heapq?
heapq 提供 heap queue 演算法 (也稱為 priority queue algorithm; 優先權佇列演算法) 的實作。Heaps 是 binary trees (二叉樹)，其中每個 parent node (父節點) 的值都小於或等於其任何 children node (子節點) 的值。此屬性使 heaps 對於實現優先權 queues 非常有用，其中具有最高優先權的項目始終位於前面。
heapq 實作了一個 min-heap，其中最小的元素始終位於 root。此 module 提供了向 heap 中添加元素、popping 最小項以及查找最小項而不 popping 它的函數。
How to Use heapq?
heapq 提供了幾個函數：
heapify(iterable)：將 iterable 轉換為 heap 資料結構。heappush(heap, item)：在 heap 中新增一個 item，保持 heap 不變。heappop(heap)：Pops 並返回 heap 中最小的 item。heappushpop(heap, item)：Pushes item 進 heap 中，然後 pops 並返回最小的項目。heapreplace(heap, item)：Pops 並返回最小的 item，然後 push 新的 item；比 heappop 和 heappush 更有效率。nlargest(n, iterable)、nsmallest(n, iterable)：傳回資料集中包含 n 個最大或最小元素的 list 。
Why Use heapq?
當您需要不斷存取 collection 中最小，最大或經過一些修改的項目時，使用 heapq 可能會很有優勢。出於此類目的，它比維護排序 list 更有效，尤其是當 list 頻繁更改時。常見 cases 包括：
實施 priority queues。
對任務進行優先排序的 scheduling algorithms (調度演算法)。
Dijkstra 和其他需要 priority queue 的 graph algorithms。
When to Use heapq?
在以下情況下應該使用 heapq：
您需要重複快速存取最小或最大的項目。
資料集是動態的，您需要高效率的插入和刪除。
實作依賴 priority queues 的演算法。
Conclusion
Python 中的 heapq module 是有效管理 heaps 和 priority queues 的強大工具。其功能簡單且針對效能進行了最佳化，使其成為基於優先順序的專案管理，必不可少的演算法和應用程式的首選。
Binary Tree, Binary Heap
Binary trees (二元樹) 是一種樹狀資料結構，其中每個 node (節點) 最多有兩個 children，稱為 left child 和 right child。以下是一些要點：
Root Node: 樹的最頂層 node。
Leaf Nodes: 沒有 children 的 node。
Depth: 從 root 到 node 的路徑長度。
Height: 從 node 到 leaf 的最長路徑的長度。
Binary Heaps
在 heapq library 的上下文中， binary tree 被組織為 binary heap。 binary heap 是一棵完全二元樹，這意味著樹的所有層都被完全填充，除了最後一層，它是從左到右填充的。
Binary heaps 有兩種類型：
Min-Heap: 每個 node 的值都大於或等於其 parent 的值，最小值元素在 root。
Max-Heap: 每個 node 的值小於或等於其 parent 的值，最大值元素在 root。
Binary heaps 數學公式和性質：
Parent Node Index: 如果一個節點位於 index
i，則其父節點位於索引(i-1)//2。Left Child Index: 對於 index
i的 node，其左子節點位於索引2*i + 1。Right Child Index: 對於 index
i的 node，其右子節點位於索引2*i + 2。
Binary heap 中 parent node index, left child index 和 right child index 的公式，適用於 min-heaps 和 max-heaps。這些公式並不是特定於 heap 的類型，而是特定於二元堆的一般結構。這些關係源自於 binary heap，作為完全 binary tree 的屬性，其中每個 level 都是從左到右填充的。
這是 binary heap 的簡單圖示：
在此 diagram 中：
1是 root node。2和3是1的 children。4和5是2的 children，6是3的 children。
heappush(), heappop(), heapreplace()
將 item 元素新增至現有的 heap 堆疊中。heappush 函數會自動調整新元素的位置以維持 heap 屬性。
heappush(heap, item)刪除並返回 heap 的最小元素。
heappop(heap)將 item 元素新增至現有的 heap 堆疊中，然後 pop 並返回 heap 中最小的項目。此函數比 heappush() 和 heappop() 的組合更有效。
heappushpop(heap, item)以新的 item 取代 heap 中的最小元素。此函數比 heappop() 和 heappush() 的組合更有效，並且在需要維護 heap 的大小，時使用。
heapreplace(heap, item)範例 – Basic Usage
Example 1: 使用 heapreplace 維護固定大小的 heap (Priority Queue)。
import heapq
heap = []
size_limit = 3
data = [5, 1, 9, 4, 3, 8]
for item in data:
if len(heap) < size_limit:
heapq.heappush(heap, item)
else:
heapq.heapreplace(heap, item)
# contains the 3 largest numbers in `data`
print(heap) # Output: [5, 8, 9]import heapq
class FixedSizeHeap:
def __init__(self, capacity):
self.heap = []
self.capacity = capacity
def push(self, item):
if len(self.heap) < self.capacity:
heapq.heappush(self.heap, item)
elif item > self.heap[0]:
heapq.heapreplace(self.heap, item)
fixed_heap = FixedSizeHeap(5)
data = [5, 7, 9, 1, 3, 8, 4, 6, 2, 0]
for num in data:
fixed_heap.push(num)
# contains the 8 largest numbers in `data`
print(fixed_heap.heap) # Output: [2, 3, 4, 6, 5, 9, 8, 7]執行結果:
Example 2: 將 heap 與自訂物件一起使用
import heapq
class Item:
def __init__(self, priority, data):
self.priority = priority
self.data = data
# Less than
def __lt__(self, other):
return self.priority < other.priority
heap = []
data = [(5, 'apple'), (1, 'banana'), (3, 'cherry')]
for priority, name in data:
heapq.heappush(heap, Item(priority, name))
print(heap)
while heap:
item = heapq.heappop(heap)
print(item.data) # Output: banana, cherry, apple執行結果:
[<__main__.Item object at 0x0000016340356E80>,
<__main__.Item object at 0x0000016340356FA0>,
<__main__.Item object at 0x0000016340356D30>]
banana
cherry
apple範例 – 計算中位數
Example 1: 使用 heapreplace 和 heappop 來執行中位數 Stream
import heapq
def add_num(num, min_heap, max_heap):
heapq.heappush(max_heap, -heapq.heappushpop(min_heap, num))
if len(max_heap) > len(min_heap):
heapq.heappush(min_heap, -heapq.heappop(max_heap))
def get_median(min_heap, max_heap):
if len(min_heap) == len(max_heap):
return (min_heap[0] - max_heap[0]) / 2.0
return min_heap[0]
min_heap = [] # min heap for the larger half
max_heap = [] # max heap for the smaller half, implemented with negated values
stream = [2, 1, 5, 7, 2, 0, 5]
for number in stream:
add_num(number, min_heap, max_heap)
print(f"Current median after adding {number}: {get_median(min_heap, max_heap)}")執行結果:
[2] []
Current median after adding 2: 2
[2] [-1]
Current median after adding 1: 1.5
[2, 5] [-1]
Current median after adding 5: 2
[5, 7] [-2, -1]
Current median after adding 7: 3.5
[2, 7, 5] [-2, -1]
Current median after adding 2: 2
[2, 7, 5] [-2, -1, 0]
Current median after adding 0: 2.0
[2, 5, 5, 7] [-2, -1, 0]
Current median after adding 5: 2該程式碼實現了一種資料結構，可以有效地即時計算數字 stream 的中位數。它使用兩個 heaps: min_heap, max_heap
add_num(num, min_heap, max_heap): 為資料結構新增一個新數字num。
Push to min heap：首先，將
numpushedmin_heap。但是，為了確保堆平衡，會將min_heap的最小的數字 (root) 彈出並推入max_heap。這是透過heapq.heappushpop(min_heap, num)完成的。保持平衡：Python 中的
max_heap是透過取負值來實現的，因為Python的heapq只支援最小 heaps。因此，我們在 pushing 和 poppingmax_heap時取反值。平衡 Heaps：如果
max_heap最終有更多元素，則max_heap中的最小數字(由於求反，實際上是最大的數字)將移動到min_heap。這可以確保兩個堆具有相同數量的元素，或min_heap多一個元素。
get_median(min_heap, max_heap): 計算目前的中位數。
偶數元素：如果兩個 heaps 的元素數量相同，則中位數是兩個 heaps 的 roots 的平均值。對於
max_heap，該值被取反。(負負得正)元素個數為奇數：如果元素個數為奇數，則中位數是
min_heap的 roots，因為它比max_heap多一個元素。
該演算法保持兩個屬性：
Size 屬性：兩個堆的大小最多相差1。
順序屬性：
min_heap中的每個元素都大於或等於max_heap中的每個元素。
中位數是兩個 root 的平均值 (如果總大小為偶數) 或min_heap的 root (如果總大小為奇數)。這是對 heaps 的巧妙利用，以確保在 O(log n) 插入 operation 之後，始終可以在 O(1) 時間內計算出中位數。
Last updated
Was this helpful?