python 堆

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

創(chuàng)建一個(gè)堆

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

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

創(chuàng)建一個(gè)堆

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

import heapq

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

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

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

插入堆

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

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

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

從堆中移除

您可以使用此功能在第一個(gè)索引處移除元素。在下面的例子中，函數(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)

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(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]