Python heapq 模块详解

什么是 heapq？

heapq 是 Python 标准库中的一个模块，用于实现最小堆（Min-Heap）。堆是一种特殊的完全二叉树，其中父节点的值总是小于或等于其子节点的值。该模块常用于实现优先队列、Top-K 问题等。

常用函数

• heapq.heappush(heap, item)：将元素推入堆中。
• heapq.heappop(heap)：弹出并返回堆中最小元素。
• heapq.heapify(x)：将列表 x 原地转换为堆。
• heapq.heappushpop(heap, item)：先 push 再 pop，效率更高。
• heapq.nlargest(n, iterable) / heapq.nsmallest(n, iterable)：返回最大/最小的 n 个元素。

基础示例

import heapq

# 创建空堆
heap = []

# 插入元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heap)  # [1, 5, 3]

# 弹出最小值
min_val = heapq.heappop(heap)
print(min_val)  # 1

实战演示：动态堆操作

点击下方按钮，观察堆的变化：

应用场景

1. 优先队列：任务调度系统中按优先级处理任务。
2. Top-K 问题：如找出访问量最高的 10 个网页。
3. 合并多个有序流：使用堆高效合并 K 个排序链表。
4. Dijkstra 算法：图中最短路径计算中使用最小堆优化。

注意事项

• heapq 实现的是最小堆。若需最大堆，可插入负值。
• 堆不保证整体有序，仅保证堆顶是最小值。
• 所有操作时间复杂度为 O(log n)，heapify 为 O(n)。