python 堆

堆是一種特殊的樹結(jié)構(gòu)，其中每個父節(jié)點小于或等于其子節(jié)點。然后它被稱為min heap。如果每個父節(jié)點大于或等于其子節(jié)點，則稱它為最大堆。實施優(yōu)先級隊列是非常有用的，在該隊列中，具有較高權(quán)重的隊列項目在處理中具有更高的優(yōu)先級。有關(guān)堆的詳細討論，請訪問我們的網(wǎng)站。如果你是頭部數(shù)據(jù)結(jié)構(gòu)的新手，請先研究它。在本章中，我們將看到使用python實現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)。

創(chuàng)建一個堆

堆是通過使用python內(nèi)建的名為heapq的庫創(chuàng)建的。該庫具有對堆數(shù)據(jù)結(jié)構(gòu)進行各種操作的相關(guān)功能。以下是這些功能的列表。

• heapify - 此函數(shù)將常規(guī)列表轉(zhuǎn)換為堆。在結(jié)果堆中，最小的元素被推到索引位置0.但其余的數(shù)據(jù)元素不一定被排序。
• heappush - 這個函數(shù)在堆中添加一個元素而不改變當前堆。
• heappop - 該函數(shù)返回堆中最小的數(shù)據(jù)元素。
• heapreplace - 該函數(shù)用函數(shù)中提供的新值替換最小的數(shù)據(jù)元素。

創(chuàng)建一個堆

通過簡單地使用具有heapify函數(shù)的元素列表來創(chuàng)建堆。在下面的例子中，我們提供了一個元素列表，heapify函數(shù)重新排列了元素到最初位置的元素。

import heapq

h = [21,1,45,78,3,5]
# use heapify to rearrange the elements
heapq.heapify(h)
print(h)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

[1, 3, 5, 78, 21, 45]

插入堆

將數(shù)據(jù)元素插入堆總是在最后一個索引處添加元素。但是，只有在值最小的情況下，您才可以再次應(yīng)用heapify函數(shù)將新添加的元素添加到第一個索引。在下面的例子中，我們插入數(shù)字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)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

從堆中移除

您可以使用此功能在第一個索引處移除元素。在下面的例子中，函數(shù)將始終刪除索引位置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)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

替換堆

heapreplace函數(shù)總是刪除堆中最小的元素，并在未被任何順序修復(fù)的地方插入新的傳入元素。

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]