堆是一種特殊的樹結構，其中每個父節點小於或等於其子節點。 然後它被稱為最小堆(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]