heapq 是 Python 的一个内置模块，提供了堆队列算法的实现，也称为优先队列算法。堆是一种特殊的二叉树结构，满足以下性质：

• 父节点的值总是小于或等于其子节点的值（最小堆）
• 每个父节点最多有两个子节点

1. 基本概念 #

在 Python 中，堆是通过列表来实现的，但需要满足堆属性。heapq 模块提供了一系列函数来操作这样的列表，使其保持堆属性。

2. 主要函数 #

2.1 heapify(iterable) #

将列表转换为堆数据结构（原地转换，线性时间复杂度）

import heapq

data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)
print(data)  # 输出: [1, 1, 2, 3, 5, 9, 4, 6]

2.2 heappush(heap, item) #

将元素推入堆中，保持堆属性

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 1)
print(heap)  # 输出: [1, 5, 2]

2.3 heappop(heap) #

弹出并返回堆中最小的元素

smallest = heapq.heappop(heap)
print(smallest)  # 输出: 1
print(heap)      # 输出: [2, 5]

2.4 heappushpop(heap, item) #

先 push 再 pop，比分开调用效率更高

result = heapq.heappushpop(heap, 3)
print(result)  # 输出: 2
print(heap)    # 输出: [3, 5]

2.5 heapreplace(heap, item) #

先 pop 再 push，与 heappushpop 顺序相反

result = heapq.heapreplace(heap, 1)
print(result)  # 输出: 3
print(heap)    # 输出: [1, 5]

2.6 nlargest(n, iterable[, key]) #

返回可迭代对象中前 n 个最大的元素

print(heapq.nlargest(3, [1, 5, 3, 9, 7]))  # 输出: [9, 7, 5]

2.7 nsmallest(n, iterable[, key]) #

返回可迭代对象中前 n 个最小的元素

print(heapq.nsmallest(3, [1, 5, 3, 9, 7]))  # 输出: [1, 3, 5]

3. 高级用法 #

3.1 自定义比较 #

可以通过元组或自定义类实现复杂比较：

# 使用元组 (priority, item)
heap = []
heapq.heappush(heap, (2, 'code'))
heapq.heappush(heap, (1, 'eat'))
heapq.heappush(heap, (3, 'sleep'))

while heap:
    print(heapq.heappop(heap))
# 输出:
# (1, 'eat')
# (2, 'code')
# (3, 'sleep')

3.2 实现最大堆 #

Python 的 heapq 模块只实现了最小堆，要实现最大堆，可以将元素取反：

nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
max_heap = []
for num in nums:
    heapq.heappush(max_heap, -num)  # 存储负数

# 获取最大元素
largest = -heapq.heappop(max_heap)
print(largest)  # 输出: 42

4. 时间复杂度 #

• heapify: O(n)
• heappush/heappop: O(log n)
• nlargest/nsmallest: O(n log k) (k 是要找的元素个数)

5. 实际应用 #

1. 优先队列：处理具有优先级的任务
2. Top K 问题：快速找出最大或最小的几个元素
3. 合并有序序列：可以高效地合并多个有序序列
4. Dijkstra 算法：用于图的最短路径计算

6. 注意事项 #

• 不要直接对列表进行操作然后期望它保持堆属性，总是使用 heapq 的函数
• 空堆上调用 heappop 或 heapreplace 会引发 IndexError
• 对于大型数据集，nlargest/nsmallest 可能比排序更高效