Python 中的堆队列 (或 heapq)
pythonserver side programmingprogramming更新于 2026/1/24 18:52:17
堆队列是一种特殊的树结构，其中每个父节点都小于或等于其子节点。在 Python 中，它是使用 heapq 模块实现的。它在实现优先级队列时非常有用，其中具有更高权重的队列项在处理时具有更高的优先级。
创建堆
堆队列是使用 Python 的内置库 heapq 创建的。该库具有对堆数据结构执行各种操作的相关函数。以下是这些函数的列表。
- heapify ——此函数将常规列表转换为堆。在生成的堆中，最小元素被推送到索引位置 0。但其余数据元素不一定已排序。
- heappush ——此函数将元素添加到堆中，而不会更改当前堆。
- heappop ——此函数返回堆中最小的数据元素。
- heapreplace ——此函数用函数中提供的新值替换最小的数据元素。
创建堆
只需使用元素列表和 heapify 函数即可创建堆。在下面的例子中，我们提供了一个元素列表，heapify 函数重新排列元素，将最小元素移到第一个位置。
示例
import heapq H = [21,1,45,78,3,5] # 使用 heapify 重新排列元素 heapq.heapify(H) print(H)
输出
执行上述代码时，会产生以下结果 −
[1, 3, 5, 78, 21, 45]
插入堆
将数据元素插入堆总是将元素添加到最后一个索引处。但是你可以再次应用 heapify 函数，仅当新添加的元素值最小时，才将其置于第一个索引。在下面的例子中，我们插入数字 8。
示例
import heapq H = [21,1,45,78,3,5] # 转换为堆 heapq.heapify(H) print(H) # 添加元素 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] # 创建堆 heapq.heapify(H) print(H) # 从堆中删除元素 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] # 创建堆 heapq.heapify(H) print(H) # 替换元素 heapq.heapreplace(H,6) print(H)
输出
执行上述代码时，会产生以下结果 −
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
