堆和优先级队列简介
优先级队列和堆非常不受欢迎，但却是非常有益的数据结构。这些数据结构为在数据集中寻找最佳元素等问题提供了非常容易使用和高效的解决方案。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() 函数用我们在参数中定义的数据元素替换列表中的数据元素。结果，最小的元素被成功替换。
