1️⃣ 概念

• 堆是一种特殊的二叉树结构：

  • 最小堆（min-heap）：父节点 ≤ 子节点 → 根节点最小
  • 最大堆（max-heap）：父节点 ≥ 子节点 → 根节点最大（Python 通过取负值实现）

• heapq 模块实现了 最小堆 的操作

• 堆常用于 优先队列、Top K 问题、动态排序 等

2️⃣ heapq常用函数

3️⃣ 基本示例

import heapq

nums = [5, 2, 9, 1, 7]

# 转成最小堆
heapq.heapify(nums)
print(nums)  # [1, 2, 9, 5, 7]  根最小

# 插入元素
heapq.heappush(nums, 3)
print(nums)  # 堆仍然保持最小堆性质

# 弹出最小元素
min_val = heapq.heappop(nums)
print(min_val, nums)

最小堆维护最小值 / 优先队列

import heapq

heap = []
heapq.heappush(heap, (2, "task2"))
heapq.heappush(heap, (1, "task1"))  # 优先级最小的先出
heapq.heappush(heap, (3, "task3"))

while heap:
    priority, task = heapq.heappop(heap)
    print(task)

输出：

task1
task2
task3

滑动窗口最大值 / 最小值

import heapq

arr = [1, 3, 5, 2, 8, 7]
k = 3
heap = arr[:k]
heapq.heapify(heap)
print(heap)  # 初始最小堆

# 滑动窗口
for i in range(k, len(arr)):
    heapq.heappushpop(heap, arr[i])
    print(heap[0])  # 当前窗口最小值

4️⃣ 求 Top K 问题

import heapq

nums = [5, 2, 9, 1, 7]

# 最大 3 个数
top3 = heapq.nlargest(3, nums)
print(top3)  # [9, 7, 5]

# 最小 3 个数
bottom3 = heapq.nsmallest(3, nums)
print(bottom3)  # [1, 2, 5]

5️⃣ 实现最大堆

Python 内置是 最小堆，最大堆可以通过取负数实现：

import heapq

nums = [5, 2, 9, 1, 7]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)

# 弹出最大元素
max_val = -heapq.heappop(max_heap)
print(max_val)  # 9

6️⃣ 优势

• 插入/弹出最小元素 O(log n)
• 获取前 K 大/小元素 O(n log k)（比排序 O(n log n) 更快）
• 内存高效，原地操作列表即可

✅ 总结：

• heapq 适合 优先队列、Top K、滑动窗口最值、动态排序 / 合并多路有序序列 等场景
• 内置最小堆，最大堆需取负数
• 与 sorted、bisect 配合也很方便