導讀
Python的強大并不在于它的文法，而在于它的庫，當你對各種資料結構感到苦惱時，Python提供了各種開箱即用的資料結構。
Python提供了關于堆的操作，下面先簡單介紹有關堆的概念。
假設有n個資料元素的序列k0, k1,…, kn-1，當且僅當滿足如下關系時，可以将這組資料稱為小頂堆（小根堆）。
ki ≤ k2i+1且ki ≤ k2i+2（其中i=0, 2,…,(n−1)/2） 複制
或者滿足如下關系時，可以将這組資料稱為大頂堆（大根堆）。
ki ≥ k2i+1且ki ≥ k2i+2（其中i=0, 2,…,(n-1)/2） 複制
對于滿足小頂堆的資料序列k0, k1,…, kn-1，如果将它們順序排成一棵完全二叉樹，則此樹的特點是：樹中所有節點的值都小于其左、右子節點的值，此樹的根節點的值必然最小。反之，對于滿足大頂堆的資料序列k0, k1,…, kn-1，如果将它們順序排成一棵完全二叉樹，則此樹的特點是：樹中所有節點的值都大于其左、右子節點的值，此樹的根節點的值必然最大。
通過上面介紹不難發現，小頂堆的任意子樹也是小頂堆，大頂堆的任意子樹還是大頂堆。
Python提供的是基于小頂堆的操作，是以Python可以對list中的元素進行小頂堆排列，這樣程式每次擷取堆中元素時，總會取得堆中最小的元素。
例如，判斷資料序列9, 30, 49, 46, 58, 79是否為堆，可以将其轉換為一棵完全二叉樹，如圖1所示。
圖1 完全二叉樹
在圖1中，每個節點上的灰色數字代表該節點資料在底層數組中的索引。圖1所示的完全二叉樹完全滿足小頂堆的特征，每個父節點的值總小于或等于它的左、右子節點的值。
Python并沒有提供“堆”這種資料類型，它是直接把清單當成堆處理的。Python提供的heapq包中有一些函數，當程式用這些函數來操作清單時，該清單就會表現出“堆”的行為。
在互動式解釋器中先導入heapq包，然後輸入heapq.__all__指令來檢視heapq包下的全部函數，可以看到如下輸出結果。
>>> heapq.__all__
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop'] 複制
上面這些函數就是執行堆操作的工具函數，這些函數的功能大緻如下。
- heappush(heap, item)：将item元素加入堆。
- heappop(heap)：将堆中最小元素彈出。
- heapify(heap)：将堆屬性應用到清單上。
- heapreplace(heap, x)：将堆中最小元素彈出，并将元素x入堆。
- merge(*iterables, key=None, reverse=False)：将多個有序的堆合并成一個大的有序堆，然後再輸出。
- heappushpop(heap, item)：将item入堆，然後彈出并傳回堆中最小的元素。
- nlargest(n, iterable, key=None)：傳回堆中最大的n個元素。
- nsmallest(n, iterable, key=None)：傳回堆中最小的n個元素。
下面程式示範了這些函數的用法。
from heapq import *
my_data = list(range(10))
my_data.append(0.5)
# 此時my_data依然是一個list清單
print('my_data的元素：', my_data)
# 對my_data應用堆屬性
heapify(my_data)
print('應用堆之後my_data的元素：', my_data)
heappush(my_data, 7.2)
print('添加7.2之後my_data的元素：', my_data) 複制
上面程式開始建立了一個list清單，接下來程式調用heapify()函數對清單執行堆操作，執行之後看到my_data的元素順序如下。
應用堆之後my_data的元素：[0, 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4] 複制
這些元素看上去是雜亂無序的，但其實并不是，它完全滿足小頂堆的特征。我們将它轉換為完全二叉樹，可以看到如圖2所示的效果。
圖2 小頂堆對應的完全二叉樹
當程式再次調用heappush(my_data, 7.2)向堆中加入一個元素之後，輸出該堆中元素，可以看到如下輸出結果。
添加7.2之後my_data的元素：[0, 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4, 7.2] 複制
此時将它轉換為完全二叉樹，可以看到如圖3所示的效果。
圖3 添加7.2之後的小頂堆對應的完全二叉樹
接下來程式嘗試從堆中彈出兩個元素。
# 彈出堆中最小的元素
print(heappop(my_data)) # 0
print(heappop(my_data)) # 0.5
print('彈出兩個元素之後my_data的元素：', my_data) 複制
上面三行代碼的輸出如下：
0
0.5
彈出兩個元素之後my_data的元素：[1, 3, 2, 7, 4, 5, 6, 7.2, 8, 9] 複制
從最後輸出的my_data的元素來看，此時my_data的元素依然滿足小頂堆的特征。
下面代碼示範了replace()函數的用法。
# 彈出最小的元素，壓入指定元素
print(heapreplace(my_data, 8.1))
print('執行replace之後my_data的元素：', my_data) 複制
執行上面兩行代碼，可以看到如下輸出結果。
1
執行replace之後my_data的元素：[2, 3, 5, 7, 4, 8.1, 6, 7.2, 8, 9] 複制
也可以測試通過nlargest()、nsmallest()來擷取最大、最小的n個元素，代碼如下。
print('my_data中最大的3個元素：', nlargest(3, my_data))
print('my_data中最小的4個元素：', nsmallest(4, my_data)) 複制
運作上面程式，可以看到如下輸出結果。
my_data中最大的3個元素：[9, 8.1, 8]
my_data中最小的4個元素：[2, 3, 4, 5] 複制
通過上面程式不難看出，Python的heapq包中提供的函數，其實就是提供對排序算法中“堆排序”的支援。Python通過在底層建構小頂堆，進而對容器中的元素進行排序，以便程式能快速地擷取最小、最大的元素，是以使用起來非常友善。
提示
當程式要擷取清單中最大的n個元素，或者最小的n個元素時，使用堆能緩存清單的排序結果，是以具有較好的性能。