Python堆

堆是一種特殊的樹結構,其中每個父節點小於或等於其子節點。 然後它被稱爲最小堆(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]
0 條評論,你可以發表評論,我們會進行改進
Comment author placeholder