堆是一種特殊的樹結(jié)構(gòu)，其中每個(gè)父節(jié)點(diǎn)小于或等于其子節(jié)點(diǎn)。 然后它被稱為最小堆(Min Heap)。 如果每個(gè)父節(jié)點(diǎn)大于或等于其子節(jié)點(diǎn)，則稱它為最大堆(Max Heap)。 實(shí)施優(yōu)先級隊(duì)列是非常有用的，在該隊(duì)列中，具有較高權(quán)重的隊(duì)列項(xiàng)目在處理中具有更高的優(yōu)先級。在本章中，我們將學(xué)習(xí)使用python實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)。

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

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

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

通過簡單地使用具有heapify函數(shù)的元素列表來創(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)

執(zhí)行上面示例代碼，得到以下結(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)

執(zhí)行上面示例代碼，得到以下結(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)

執(zhí)行上面示例代碼，得到以下結(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)

執(zhí)行上面示例代碼，得到以下結(jié)果 -

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