python 堆

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