Python heapq模塊

堆和優先級隊列簡介

優先級隊列和堆非常不受歡迎，但卻是非常有益的數據結構。這些數據結構為在數據集中尋找最佳元素等問題提供了非常容易使用和高效的解決方案。Python 的 heapq 模塊是其標準庫的一部分。這個模塊實現了所有的低級堆操作和一些常見的高級堆利用。

像優先級隊列這樣的數據結構在解決諸如編寫電子郵件調度程序、合併日誌文件或在地圖上尋找最短路徑等問題時，作為一個強大的工具發揮着重要作用。眾所周知，編程充滿了問題優化，目標是找到最佳元素和優先級隊列，而 Python heapq 模塊中的函數通常可以作為解決方案。

在下面的教程中，我們將學習什麼是堆和優先級隊列，以及它們如何相互關聯。我們還將發現使用堆可以解決什麼類型的問題，以及我們如何使用 Python heapq 模塊來解決這些問題。

讓我們從理解堆開始。

理解堆

堆是具體的數據結構，優先級隊列是抽象的數據結構。具體的數據結構表示實現，而抽象的數據結構控制接口。

我們通常使用堆來實現優先級隊列。它們是最著名的具體數據結構，用於實現抽象數據結構，如優先級隊列。

具體的數據結構也表明了性能保證。性能保證確保了結構大小和操作所用時間之間的關係。這些性能保證允許我們預測當輸入大小改變時程序所花費的時間。

理解 Python 中的 heapq模塊

眾所周知，數據結構“堆”通常用於表示優先級隊列。我們可以使用 Python 標準庫中的 heapq 模塊來執行這個實現。Python 中堆數據結構的屬性是每次彈出最小的堆元素( min-heap )。每當彈出或推送數據元素時，都會維護堆結構。堆[0] 元素每次也傳遞最小的數據元素。

讓我們了解堆上的一些操作:

| 南號碼 | 操作還是功能 | 描述 |
| 1 | heapify(可滴定) | heapify() 功能用於將可迭代轉換為堆數據結構。 |
| 2 | heappush(堆，元素) | heappush() 功能用於將參數中指定的數據元素插入到堆中。可以調整順序來維護堆結構。 |
| 3 | heap(堆) | heappop() 功能用於從堆中移除並返回最小的數據元素。也可以調整順序來維護堆結構。 |
| 4 | heappushppop(堆，元素) | heappushppop()功能用於將推送和彈出操作結合在一個語句中，從而提高效率。一旦操作完成，堆順序就保持不變。 |
| 5 | 堆位置(堆，元素) | heapreplace() 功能用於在單個語句中插入和彈出數據元素；然而，它不同於上述功能。在這個函數中，首先彈出數據元素，然後推送數據元素。因此，可以返回比推送元素的值更突出的元素的值。 heapreplace() 函數用於真正返回堆中的最小值，而不考慮推送的元素，而不是heappushppop()函數。 |
| 6 | n 目標(x，可迭代，必不可少=樂趣) | nlargetist()功能用於從可迭代返回最顯著的元素 x ，確定該元素是否也滿足鍵。 |
| 7 | n 最小(x，可迭代，key = fun) | nsmalest()功能用於從可迭代中返回微量元素 x ，如果包含該元素，則該元素也滿足鍵。 |

現在，讓我們在接下來的章節中了解 heapq 模塊的這些功能的工作原理。

創建堆

藉助 heapify() 函數，我們可以利用數據元素列表創建一個堆。讓我們考慮一個例子來理解 heapify() 函數的工作原理，其中提供了一個數據元素列表，該函數重新排列數據元素。它將最小的元素帶到第一個位置。

示例:

# importing the heapq module
import heapq

# defining a list
mylist = [14, 23, 4, 43, 34, 9, 18, 1, 25, 8]

# Using the heapify() function to rearrange the data elements
heapq.heapify(mylist)

# printing the list
print(mylist)

輸出:

[1, 8, 4, 23, 14, 9, 18, 43, 25, 34]

說明:

在上面的例子中，我們已經導入了 heapq 模塊，並定義了一個數據元素列表。然後我們使用 heapify() 函數來重新排列數據元素，將最小的數據元素放到第一個位置。最後，我們為用戶打印了列表。結果，列表中的數據元素被重新排列，最小的元素被帶到第一個位置。

現在讓我們嘗試將數據元素插入堆中。

將數據元素插入堆中

我們可以使用 heappush() 函數將數據元素插入堆中。插入列表的元素總是添加到最後一個索引中。然而，我們可以再次使用 heapify() 函數，以便僅當新插入的數據元素看起來是值中最小的時，才將其帶到第一個索引。讓我們考慮一個演示 heappush() 函數工作的例子。

示例:

# importing the heapq module
import heapq

# defining a list
mylist = [14, 23, 4, 43, 34, 9, 18, 1, 25, 8]

# Using the heapify() function to rearrange the data elements
heapq.heapify(mylist)

# printing the list
print(mylist)

# inserting element to the list
heapq.heappush(mylist, 20)

# printing the final list
print(mylist)

輸出:

[1, 8, 4, 23, 14, 9, 18, 43, 25, 34]
[1, 8, 4, 23, 14, 9, 18, 43, 25, 34, 20]

說明:

在上面的例子中，我們再次導入了 heapq 模塊並定義了一個列表。然後，我們將列錶轉換為堆，並將列表打印給用戶。然後，我們使用 heappush() 函數向列表中添加新元素，並為用戶打印最終列表。因此，新的數據元素被插入到列表的最後一個索引處。

現在，讓我們嘗試從堆中移除元素。

從堆中移除數據元素

我們可以藉助 heappop() 函數刪除第一個索引處的數據元素。讓我們考慮下面的例子來理解刪除數據元素的過程是如何進行的。

示例:

# importing the heapq module
import heapq

# defining a list
mylist = [14, 23, 4, 43, 34, 9, 18, 1, 25, 8]

# Using the heapify() function to rearrange the data elements
heapq.heapify(mylist)

# printing the list
print(mylist)

# inserting element to the list
heapq.heappop(mylist)

# printing the final list
print(mylist)

輸出:

[1, 8, 4, 23, 14, 9, 18, 43, 25, 34]
[4, 8, 9, 23, 14, 34, 18, 43, 25]

說明:

在上面的例子中，我們再次導入了 heapq 模塊，定義了一個列表，並將其轉換為一個堆。然後，我們使用 heappop() 函數從列表中移除第一個索引元素。因此，該元素被成功移除。

現在，讓我們了解如何替換堆中的元素

替換堆中的數據元素

為了替換一個數據元素，我們可以使用 heapreplace() 函數。該函數總是刪除堆中最小的數據元素，並在順序中未定義的地方添加新的傳入元素。

讓我們考慮一個例子來理解替換堆中元素的概念。

示例:

# importing the heapq module
import heapq

# defining a list
mylist = [14, 23, 4, 43, 34, 9, 18, 1, 25, 8]

# Using the heapify() function to rearrange the data elements
heapq.heapify(mylist)

# printing the list
print(mylist)

# replacing element in the list
heapq.heapreplace(mylist, 99)

# printing the final list
print(mylist)

輸出:

[1, 8, 4, 23, 14, 9, 18, 43, 25, 34]
[4, 8, 9, 23, 14, 99, 18, 43, 25, 34]

說明:

在上面的例子中，我們再次導入了 heapq 模塊，定義了一個列表，並創建了堆。然後，我們使用 heapreplace() 函數用我們在參數中定義的數據元素替換列表中的數據元素。結果，最小的元素被成功替換。