heapq --- 堆積佇列 (heap queue) 演算法

原始碼：Lib/heapq.py

這個模組實作了堆積佇列 (heap queue) 演算法，亦被稱為優先佇列 (priority queue) 演算法。

最小堆積 (min-heap) 是一顆二元樹，樹上每個父節點的值都小於或等於其子節點的值。我們將這種情況稱為堆積性質不變 (heap invariant)。

對於最小堆積，此實作使用串列，對於所有存在的被比較元素，k 都滿足 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]。元素是從零開始計數。最小堆積有一個有趣的性質：最小的元素永遠在根節點 heap[0]。

Max-heaps satisfy the reverse invariant: every parent node has a value greater than any of its children. These are implemented as lists for which maxheap[2*k+1] <= maxheap[k] and maxheap[2*k+2] <= maxheap[k] for all k for which the compared elements exist. The root, maxheap[0], contains the largest element; heap.sort(reverse=True) maintains the max-heap invariant.

heapq API 與教科書上的堆積演算法在兩個方面不同：(a) 我們使用從零開始的索引。這使得節點索引和其子節點索引之間的關係變得不那麼明顯，但由於 Python 使用從零開始的索引，所以這樣更適合。(b) 教科書通常專注於最大堆積，因為它們適合原地排序。我們的實作偏向於最小堆積，因為它們更符合 Python 串列。

這兩個特性使得可以將堆積視為一個普通的 Python 串列而不會有意外：heap[0] 是最小的元素，而 heap.sort() 維持堆積性質不變！

Like list.sort(), this implementation uses only the < operator for comparisons, for both min-heaps and max-heaps.

In the API below, and in this documentation, the unqualified term heap generally refers to a min-heap. The API for max-heaps is named using a _max suffix.

要建立一個堆積，使用初始化為 [] 的串列，或者分別使用 heapify() 或 heapify_max() 函式將現有的串列轉換為最小堆積或最大堆積。

提供了以下針對最小堆積的函式：

heapq.heapify(x)

在線性時間內將串列 x 原地轉換為最小堆積。

heapq.heappush(heap, item)

將值 item 推入 heap，並維持最小堆積性質不變。

heapq.heappop(heap)

從 heap 取出並回傳最小的元素，維持最小堆積性質不變。如果堆積為空，會引發 IndexError。若要在不取出的情況下存取最小元素，請使用 heap[0]。

heapq.heappushpop(heap, item)

將 item 放入 heap ，接著從 heap 取出並回傳最小的元素。這個組合函式比呼叫 heappush() 之後呼叫 heappop() 更有效率。

heapq.heapreplace(heap, item)

從 heap 取出並回傳最小的元素，接著將新的 item 放進heap。heap 的大小不會改變。如果 heap 是空的會產生 IndexError 錯誤。

這個一次完成的操作會比呼叫 heappop() 之後呼叫 heappush() 更有效率，並在維護 heap 的大小不變時更為適當，取出/放入的組合函式一定會從 heap 回傳一個元素並用 item 取代他。

函式的回傳值可能會大於被加入的 item 。如果這不是你期望發生的，可以考慮使用 heappushpop() 替代，他會回傳 heap 的最小值和 item 兩個當中比較小的那個，並將大的留在 heap 內。

提供以下針對最大堆積的函式：

heapq.heapify_max(x)

在線性時間內將串列 x 原地轉換為最大堆積。

在 3.14 版被加入.

heapq.heappush_max(heap, item)

將值 item 推入最大堆積 heap，維持最大堆積性質不變。

在 3.14 版被加入.

heapq.heappop_max(heap)

從最大堆積 heap 取出並回傳最大的元素，維持最大堆積性質不變。如果最大堆積為空，會引發 IndexError。若要在不取出的情況下存取最大元素，請使用 maxheap[0]。

在 3.14 版被加入.

heapq.heappushpop_max(heap, item)

將 item 推入 max-heap heap，然後取出並回傳 heap 中最大的元素。這個組合動作比先呼叫 heappush_max() 再單獨呼叫 heappop_max() 更有效率。

在 3.14 版被加入.

heapq.heapreplace_max(heap, item)

從最大堆積 heap 取出並回傳最大的元素，同時推入新的 item。最大堆積的大小不會改變。如果最大堆積為空，會引發 IndexError。

The value returned may be smaller than the item added. Refer to the analogous function heapreplace() for detailed usage notes.

在 3.14 版被加入.

這個模組也提供三個利用 heap 實作的一般用途函式

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

合併多個已排序的輸入並產生單一且已排序的輸出（舉例：合併來自多個 log 檔中有時間戳記的項目）。回傳一個 iterator 包含已經排序的值。

和 sorted(itertools.chain(*iterables)) 類似但回傳值是一個 iterable ，不會一次把所有資料都放進記憶體中，並且假設每一個輸入都已經（由小到大）排序過了。

有兩個選用參數，指定時必須被當作關鍵字參數指定。

key 參數指定了一個 key function 引數，用來從每一個輸入的元素中決定一個比較的依據。預設的值是 None （直接比較元素）。

reverse 是一個布林值，如果設定為 True ，則輸入的元素將以相反的比較順序進行合併。為了達成類似 sorted(itertools.chain(*iterables), reverse=True) 的行為，所有 iterables 必須由大到小排序。

在 3.5 版的變更: 加入選用參數 key 和 reverse 。

heapq.nlargest(n, iterable, key=None)

回傳一個包含資料 iterable 中前 n 大元素的 list 。如果有指定 key 引數，key 會是只有一個引數的函式，用來從每一個在 iterable 中的元素提取一個比較的依據（例如 key=str.lower ）。效果相當於 sorted(iterable, key=key, reverse=True)[:n] 。

heapq.nsmallest(n, iterable, key=None)

回傳一個包含資料 iterable 中前 n 小元素的 list 。如果有指定 key 引數，key 會是只有一個引數的函式，用來從每一個在 iterable 中的元素提取一個比較的依據（例如 key=str.lower ）。效果相當於 sorted(iterable, key=key)[:n] 。

後兩個函式在 n 值比較小時有最好的表現。對於較大的 n 值，只用 sorted() 函式會更有效率。同樣地，當 n==1 時，使用內建函式 min() 和 max() 會有更好的效率。如果需要重複使用這些函式，可以考慮將 iterable 轉成真正的 heap 。

基礎範例

堆積排序 (heapsort) 可以透過將所有的值推入一個 heap，並且從 heap 中一個接一個彈出最小元素來實作：

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9