> For the complete documentation index, see [llms.txt](https://docs.xiwind-corp.com/tech/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.xiwind-corp.com/tech/python-library/heapq-dui-ji-zhu-lie.md).

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

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

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

### 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。

{% hint style="info" %}
Python 的 `heapq` module 實作了 min-heap。
{% endhint %}

**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 的簡單圖示：**

{% @mermaid/diagram content="graph TD
A((1))
B((2))
C((3))
D((4))
E((5))
F((6))

```
A --> B
A --> C
B --> D
B --> E
C --> F" %}
```

在此 diagram 中：

* `1` 是 root node。
* `2` 和 `3` 是 `1` 的 children。
* `4` 和 `5` 是 `2` 的 children，`6` 是 `3` 的 children。

## heappush(), heappop(), heapreplace()

***

將 `item` 元素新增至現有的 `heap` 堆疊中。`heappush` 函數會自動調整新元素的位置以維持 heap 屬性。

{% code title="PYTHON" %}

```python
heappush(heap, item)
```

{% endcode %}

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

{% code title="PYTHON" %}

```python
heappop(heap)
```

{% endcode %}

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

{% code title="PYTHON" %}

```python
heappushpop(heap, item)
```

{% endcode %}

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

{% code title="PYTHON" %}

```python
heapreplace(heap, item)
```

{% endcode %}

{% hint style="info" %}
**最小的元素總是在 root (`heap[0]`)。若要按排序順序取得所有元素，請連續使用 `heappop()`。**
{% endhint %}

{% hint style="info" %}
**如果您需要 max heap (頂部的最大元素)，您可以透過否定它們，來反轉優先權。**
{% endhint %}

{% hint style="info" %}
**Python 的 `heapq` 模組僅提供 min heap 實作。對於 max heap 可以:**

1. 對值取反值是
2. 對第一個元素是取反值
3. 使用 tuples 自訂 comparator (比較器)。
   {% endhint %}

{% hint style="info" %}
**Heaps 不會保持具有相同 keys 的元素的穩定性 (即，它們的原始 order 可能不會被保留)。**

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

### 範例 – Basic Usage

***

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

{% code title="PYTHON" %}

```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]
```

{% endcode %}

{% code title="PYTHON" %}

```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]
```

{% endcode %}

**執行結果:**

{% @mermaid/diagram content="graph TD
A\[2] --> B\[3]
A --> C\[4]
B --> D\[6]
B --> E\[5]
C --> F\[9]
C --> G\[8]
D --> H\[7]" %}

**Example 2: 將 heap 與自訂物件一起使用**

{% code title="PYTHON" %}

```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
```

{% endcode %}

**執行結果:**

```txt
[<__main__.Item object at 0x0000016340356E80>, 
 <__main__.Item object at 0x0000016340356FA0>, 
 <__main__.Item object at 0x0000016340356D30>]
 
banana
cherry
apple
```

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

### 範例 – 計算中位數

***

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

{% code title="PYTHON" %}

```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)}")
```

{% endcode %}

**執行結果:**

```txt
[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)` 時間內計算出中位數。<br>