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 提供了幾個函數：

1. heapify(iterable)：將 iterable 轉換為 heap 資料結構。

2. heappush(heap, item)：在 heap 中新增一個 item，保持 heap 不變。

3. heappop(heap)：Pops 並返回 heap 中最小的 item。

4. heappushpop(heap, item)：Pushes item 進 heap 中，然後 pops 並返回最小的項目。

5. heapreplace(heap, item)：Pops 並返回最小的 item，然後 push 新的 item；比 heappop 和 heappush 更有效率。

6. 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 的演算法。

Heaps 非常適合需要頻繁訪問最小或最大元素，以及資料集動態變化的應用程序，特別是當元素的順序很重要時 (例如在優先級佇列中)。

Lists 非常適合需要透過 index 頻繁存取元素，或元素大多在末尾新增/刪除的場景。

Conclusion

Python 中的 heapq module 是有效管理 heaps 和 priority queues 的強大工具。其功能簡單且針對效能進行了最佳化，使其成為基於優先順序的專案管理，必不可少的演算法和應用程式的首選。

Binary Tree, Binary Heap

---

Binary trees (二元樹) 是一種樹狀資料結構，其中每個 node (節點) 最多有兩個 children，稱為 left child 和 right child。以下是一些要點：

1. Root Node: 樹的最頂層 node。

2. Leaf Nodes: 沒有 children 的 node。

3. Depth: 從 root 到 node 的路徑長度。

4. Height: 從 node 到 leaf 的最長路徑的長度。

Binary Heaps

在 heapq library 的上下文中， binary tree 被組織為 binary heap。 binary heap 是一棵完全二元樹，這意味著樹的所有層都被完全填充，除了最後一層，它是從左到右填充的。

Binary heaps 有兩種類型：

1. Min-Heap: 每個 node 的值都大於或等於其 parent 的值，最小值元素在 root。

2. Max-Heap: 每個 node 的值小於或等於其 parent 的值，最大值元素在 root。

Python 的 heapq module 實作了 min-heap。

Binary heaps 數學公式和性質：

1. Parent Node Index: 如果一個節點位於 index i ，則其父節點位於索引 (i-1)//2。

2. Left Child Index: 對於 index i 的 node，其左子節點位於索引 2*i + 1。

3. 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 屬性。

PYTHON

heappush(heap, item)

刪除並返回 heap 的最小元素。

PYTHON

heappop(heap)

將 item 元素新增至現有的 heap 堆疊中，然後 pop 並返回 heap 中最小的項目。此函數比 heappush() 和 heappop() 的組合更有效。

PYTHON

heappushpop(heap, item)

以新的 item 取代 heap 中的最小元素。此函數比 heappop() 和 heappush() 的組合更有效，並且在需要維護 heap 的大小，時使用。

PYTHON

heapreplace(heap, item)

最小的元素總是在 root (heap[0])。若要按排序順序取得所有元素，請連續使用 heappop()。

如果您需要 max heap (頂部的最大元素)，您可以透過否定它們，來反轉優先權。

Python 的 heapq 模組僅提供 min heap 實作。對於 max heap 可以:

1. 對值取反值是

2. 對第一個元素是取反值

3. 使用 tuples 自訂 comparator (比較器)。

Heaps 不會保持具有相同 keys 的元素的穩定性 (即，它們的原始 order 可能不會被保留)。

如果穩定性很重要，請考慮排序或使用其他方法。

範例 – Basic Usage

---

Example 1: 使用 heapreplace 維護固定大小的 heap (Priority Queue)。

PYTHON

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]

PYTHON

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 與自訂物件一起使用

PYTHON

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

在使用複雜的資料結構 (如物件或 tuples) 時，請確保它們是可比較的。 Python's heap operations 會比較元素，因此 heap 的元素應該支援比較。

範例 – 計算中位數

---

Example 1: 使用 heapreplace 和 heappop 來執行中位數 Stream

PYTHON

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。

1. Push to min heap：首先，將 num pushed min_heap。但是，為了確保堆平衡，會將 min_heap 的最小的數字 (root) 彈出並推入max_heap。這是透過 heapq.heappushpop(min_heap, num) 完成的。

2. 保持平衡：Python 中的 max_heap 是透過取負值來實現的，因為Python的 heapq 只支援最小 heaps。因此，我們在 pushing 和 popping max_heap 時取反值。

3. 平衡 Heaps：如果 max_heap 最終有更多元素，則 max_heap 中的最小數字(由於求反，實際上是最大的數字)將移動到min_heap。這可以確保兩個堆具有相同數量的元素，或min_heap多一個元素。

• get_median(min_heap, max_heap): 計算目前的中位數。

1. 偶數元素：如果兩個 heaps 的元素數量相同，則中位數是兩個 heaps 的 roots 的平均值。對於 max_heap，該值被取反。(負負得正)

2. 元素個數為奇數：如果元素個數為奇數，則中位數是 min_heap 的 roots，因為它比 max_heap 多一個元素。

• 該演算法保持兩個屬性：

1. Size 屬性：兩個堆的大小最多相差1。

2. 順序屬性：min_heap中的每個元素都大於或等於max_heap中的每個元素。

中位數是兩個 root 的平均值 (如果總大小為偶數) 或min_heap的 root (如果總大小為奇數)。這是對 heaps 的巧妙利用，以確保在 O(log n) 插入 operation 之後，始終可以在 O(1) 時間內計算出中位數。