Python - 堆

---

---

堆是一種特殊的樹形結構，其中每個父節點都小於或等於其子節點。如果是這樣，則稱為最小堆。如果每個父節點都大於或等於其子節點，則稱為最大堆。它在實現優先佇列方面非常有用，在優先佇列中，權重較高的佇列項在處理中具有更高的優先順序。

關於堆的詳細討論可在我們的網站上找到。如果您不熟悉堆資料結構，請先學習它。在本節中，我們將學習使用 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]

在堆中替換

堆替換函式始終刪除堆中最小的元素，並將新的傳入元素插入到某個位置（該位置沒有固定的順序）。

示例

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]