python优先队列使用

heapq 是 Python 的一个内置模块，提供了堆队列算法的实现，也称为优先队列算法。以下是关于 heapq 模块的详细使用说明。

基本概念

• 堆：一种特殊的二叉树结构，满足父节点总是小于或等于其子节点（最小堆）
• 特性：
  • 堆是一个完全二叉树
  • 堆中每个节点的值都小于或等于其子节点的值（最小堆）
  • 根节点总是堆中的最小元素

1. 添加元素

heap = []
heapq.heappush(heap, 5)    # 添加元素
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print(heap)  # 输出可能是 [1, 3, 7, 5]

2. 弹出最小元素

smallest = heapq.heappop(heap)
print(smallest)  # 输出 1
print(heap)      # 输出可能是 [3, 5, 7]

3. 查看最小元素（不弹出）

smallest = heap[0]
print(smallest)  # 输出 3

4. 合并堆

heap1 = [1, 3, 5]
heap2 = [2, 4, 6]
merged = list(heapq.merge(heap1, heap2))  # 返回一个迭代器
print(list(merged))  # 输出 [1, 2, 3, 4, 5, 6]