推荐直接看网页和本页的heapq库：
8.1   堆 - Hello 算法

基于堆更加高效地解决 Top-k 问题，流程

堆化（Heapify），即建堆操作：如何从一个无序数组或不符合堆性质的完全二叉树构建堆

堆化的核心操作是 heapify_down（下沉） 或 heapify_up（上浮），这两个都是强调修复和单个元素，通过递归或迭代调整节点位置，最终使整个数据结构满足堆性质。

Top-k 问题

问题：给定一个长度为n的无序数组 nums ，请返回数组中最大的k个元素。
步骤：

  1. 初始化一个小顶堆，其堆顶元素最小。
  2. 先将数组的前k个元素依次入堆。
  3. 从第k个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆(最小元素出堆)。
  4. 遍历完成后，堆中保存的就是最大的k个元素。
    复杂度：
      n轮入堆和出堆，堆的最大长度为 k，因此时间复杂度为nlogk

python的heapq（堆队列）库

用法：注意，heapq借助原生的数组实现！！而不是heapq()！

Python 的 heapq 模块提供了基于堆的优先队列实现，支持最小堆（Min Heap）操作。以下是 heapq 的核心用法及常见场景示例：

1. 基本操作

1.1 将列表转换为堆（原地修改）

1
2
3
4
5
import heapq

data = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(data)# 将列表转为最小堆，时间复杂度 O(n)
print(data)# 输出: [1, 1, 2, 3, 5, 9, 4]（堆结构，非完全排序）

1.2 插入元素（heappush）

1
2
heapq.heappush(data, 0)# 插入元素并维护堆性质，O(log n)
print(data)# 输出: [0, 1, 1, 3, 5, 9, 4, 2]

1.3 弹出最小元素（heappop）

1
2
3
min_val = heapq.heappop(data)# 弹出并返回最小值，O(log n)
print(min_val)# 输出: 0
print(data)# 输出: [1, 1, 2, 3, 5, 9, 4]

2. 高级操作

2.1 获取前 N 个最小/最大元素

1
2
3
4
5
6
7
# 获取前3个最小值（无需修改原列表）
smallest = heapq.nsmallest(3, data)
print(smallest)# 输出: [1, 1, 2]

# 获取前2个最大值
largest = heapq.nlargest(2, data)
print(largest)# 输出: [9, 5]

2.2 合并多个有序堆

1
2
3
4
heap1 = [1, 3, 5]
heap2 = [2, 4, 6]
merged = list(heapq.merge(heap1, heap2))# 合并后仍有序
print(merged)# 输出: [1, 2, 3, 4, 5, 6]

2.3 自定义优先级（元组排序）

1
2
3
4
5
6
7
8
9
10
tasks = [(2, 'task1'), (1, 'task2'), (3, 'task3')]
heapq.heapify(tasks)# 按元组第一个元素（优先级）排序

while tasks:
	priority, task = heapq.heappop(tasks)
	print(f"执行任务: {task} (优先级: {priority})")
# 输出:
# 执行任务: task2 (优先级: 1)
# 执行任务: task1 (优先级: 2)
# 执行任务: task3 (优先级: 3)

3. 注意事项

  1. 最小堆特性：
    heapq 仅实现最小堆，如需最大堆，可将数值取反存储（如 push -x，弹出时再取反）。

    1
    2
    3
    4
    data = [3, 1, 4]
    max_heap = [-x for x in data]
    heapq.heapify(max_heap)
    max_val = -heapq.heappop(max_heap)# 弹出最大值 4

  2. 原地修改：
    heapify、heappush、heappop 直接修改原列表，不返回新列表。

  3. 时间复杂度：

  • heapify: O(n)
  • heappush/heappop: O(log n)
  • nsmallest/nlargest: O(n log k)（k 为前 N 个元素）

4. 完整示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq

# 模拟任务调度
tasks = []
heapq.heappush(tasks, (3, "Low priority task"))
heapq.heappush(tasks, (1, "Urgent task"))
heapq.heappush(tasks, (2, "Normal task"))

while tasks:
	priority, task = heapq.heappop(tasks)
	print(f"[优先级 {priority}] {task}")

# 输出:
# [优先级 1] Urgent task
# [优先级 2] Normal task
# [优先级 3] Low priority task

总结

heapq 是 Python 中高效的堆实现，适用于：

  • 优先队列（按优先级处理任务）
  • Top-K 问题（快速获取前 N 个极值）
  • 合并有序序列（如多路归并）

通过灵活使用元组和取反技巧，可以覆盖大多数场景需求。