Python heapq模块

堆和优先级队列简介

优先级队列和堆是非常不受欢迎但非常有用的数据结构。这些数据结构为诸如在数据集中查找最佳元素等问题提供了非常用户友好且高效的解决方案。 Python 的 heapq 模块是标准库的一部分。该模块实现了所有低级堆操作和一些常见的高级堆利用。

在解决编写电子邮件调度程序、合并日志文件或在地图上查找最短路径等问题时，优先级队列等数据结构作为强大的工具发挥着重要作用。众所周知，编程充满了优化问题，其目标是找到最优元素和优先级队列，而Python heapq模块中的函数通常可以充当解决方案。

在下面的教程中，我们将了解什么是堆和优先级队列以及它们之间的关系。我们还将发现使用堆可以解决哪些类型的问题以及如何使用 Python heapq 模块来解决这些问题。

让我们从了解堆开始。

了解桩

堆是具体的数据结构，优先级队列是抽象的数据结构。具体的数据结构代表实现，而抽象数据结构控制接口。

我们通常使用堆来实现优先级队列。它们是最著名的具体数据结构，用于实现优先级队列等抽象数据结构。

特定的数据结构也表明了性能保证。性能保证确保了施工规模和运营时间之间的关系。这些性能保证使我们能够预测当输入大小发生变化时程​​序将花费多长时间。

了解 Python 中的 heapq模块

众所周知，数据结构“堆”通常用来表示优先级队列。我们可以使用Python标准库中的heapq模块来执行此实现。 Python中堆数据结构的特性是每次弹出最小的堆元素（min-heap）。每次推送或压入数据项时，都会维护堆结构。 Heap[0] 元素每次也会传递到最小的数据元素。

我们来了解一下堆上的一些操作：

|南号|操作或功能|描述 | | 1 | heapify（可滴定）| heapify() 函数用于将可迭代对象转换为堆数据结构。 | | 2 | heappush（堆，元素）| heappush()函数用于将参数中指定的数据元素插入到堆中。可以调整顺序以维持堆结构。| | 3 |堆（堆）| heappop() 函数用于从堆中删除并返回最小的数据项。还可以调整顺序以维持堆结构。 | | 4 | heappushppop（堆，元素）| heappushppop()函数用于将push和pop操作合并在一条语句中，以提高效率。当操作完成时，堆顺序保持不变。 | | 5 | heapPosition(堆, 元素) | 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() 函数将列表中的数据项替换为我们在参数中定义的数据项。结果，最小的元素被替换。

---