Python堆
堆是一種特殊的樹結構，其中每個父節點小於或等於其子節點。 然後它被稱爲最小堆(Min Heap)。 如果每個父節點大於或等於其子節點，則稱它爲最大堆(Max Heap)。 實施優先級隊列是非常有用的，在該隊列中，具有較高權重的隊列項目在處理中具有更高的優先級。在本章中，我們將學習使用python實現堆數據結構。
創建一個堆
堆是通過使用python內建的名稱爲heapq的庫創建的。 該庫具有對堆數據結構進行各種操作的相關功能。 以下是這些函數的列表 -
-
heapify- 此函數將常規列表轉換爲堆。 在結果堆中，最小的元素被推到索引位置0。但是其餘的數據元素不一定被排序。 -
heappush- 這個函數在堆中添加一個元素而不改變當前堆。 -
heappop- 該函數返回堆中最小的數據元素。 -
heapreplace- 該函數用函數中提供的新值替換最小的數據元素。
通過簡單地使用具有heapify函數的元素列表來創建堆。 在下面的例子中，提供了一個元素列表，heapify函數重新排列了元素到最初位置的元素。
import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)執行上面示例代碼，得到以下結果 -
[1, 3, 5, 78, 21, 45]插入堆
將數據元素插入堆總是在最後一個索引處添加元素。 但是，只有在值最小的情況下，纔可以再次應用heapify函數將新添加的元素添加到第一個索引。 在下面的例子中，插入數字 - 8 。
import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)執行上面示例代碼，得到以下結果 -
[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]從堆中移除
可以使用此功能在第一個索引處移除元素。 在下面的例子中，函數將始終刪除索引位置1處的元素。
import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Remove element from the heap
heapq.heappop(H)
print(H)執行上面示例代碼，得到以下結果 -
[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]替換堆
heapreplace函數總是刪除堆中最小的元素，並在未被任何順序修復的地方插入新的傳入元素。參考以下示例 -
import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Replace an element
heapq.heapreplace(H,6)
print(H)執行上面示例代碼，得到以下結果 -
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]