04-数据结构与算法
难度：⭐⭐⭐ 专家 预计时间：40分钟 前置知识：列表操作、排序算法基础、时间复杂度概念 引入版本：Python 2.3+
本章讲解 heapq 和 bisect 模块，掌握堆队列算法和二分查找，解决优先级队列和有序列表维护问题。
为什么需要 heapq 和 bisect？
问题场景
你正在开发一个任务调度系统，需要按优先级执行任务：
python
class TaskScheduler:
def __init__(self) -> None:
self._tasks: list[Task] = []
def add_task(self, task: Task) -> None:
self._tasks.append(task)
self._tasks.sort(key=lambda t: t.priority) # 每次都全排序
def get_next_task(self) -> Task | None:
if self._tasks:
return self._tasks.pop(0) # O(n) 移动
return None
class Task:
def __init__(self, name: str, priority: int) -> None:
self.name = name
self.priority = priority
scheduler = TaskScheduler()
scheduler.add_task(Task("发邮件", 2))
scheduler.add_task(Task("紧急修复", 1))
scheduler.add_task(Task("生成报表", 3))
print(f"下一个任务: {scheduler.get_next_task().name}")问题：
- 每次添加任务都要全排序，O(n log n)
- 弹出任务需要移动列表，O(n)
- 数据频繁变动时效率低下
堆队列解决方案：
python
import heapq
from dataclasses import dataclass, field
@dataclass(order=True)
class Task:
priority: int
name: str = field(compare=False)
class TaskScheduler:
def __init__(self) -> None:
self._tasks: list[Task] = []
def add_task(self, task: Task) -> None:
heapq.heappush(self._tasks, task) # O(log n)
def get_next_task(self) -> Task | None:
if self._tasks:
return heapq.heappop(self._tasks) # O(log n)
return None
scheduler = TaskScheduler()
scheduler.add_task(Task(2, "发邮件"))
scheduler.add_task(Task(1, "紧急修复"))
scheduler.add_task(Task(3, "生成报表"))
while task := scheduler.get_next_task():
print(f"执行: {task.name} (优先级: {task.priority})")这就是 heapq 的价值：高效维护优先级队列，插入和弹出都是 O(log n)。
概念铺垫
┌─────────────────────────────────────────────────────────────┐
│ heapq 和 bisect 核心概念 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. heapq：堆队列算法 │
│ ───────────────────────────────────────────── │
│ • 用途：高效获取最大/最小值、维护优先级队列 │
│ • 特点：小顶堆，堆顶永远是最小值 │
│ • 复杂度：插入/弹出 O(log n)，建堆 O(n) │
│ • 生活类比：体检排队（紧急者优先） │
│ │
│ 2. bisect：二分查找算法 │
│ ───────────────────────────────────────────── │
│ • 用途：在有序列表中快速查找插入位置 │
│ • 特点：前提是列表必须已排序 │
│ • 复杂度：查找 O(log n)，插入仍 O(n)（列表移动） │
│ • 生活类比：字典翻页（二分定位） │
│ │
│ 3. 与原生列表的对比 │
│ ───────────────────────────────────────────── │
│ 操作 原生列表 heapq bisect │
│ 获取最小值 O(n) O(1) 不适用 │
│ 插入元素 O(1) O(log n) O(n) │
│ 弹出最小值 O(n) O(log n) 不适用 │
│ 查找位置 O(n) 不适用 O(log n) │
│ 全排序 O(n log n) 不适用 不适用 │
│ │
│ 4. 适用场景 │
│ ───────────────────────────────────────────── │
│ heapq： │
│ • 优先级队列、任务调度 │
│ • Top K 问题（最大/最小 N 个元素） │
│ • 数据流中实时维护极值 │
│ │
│ bisect： │
│ • 维护有序列表（减少全排序） │
│ • 区间映射（分数定级、价格区间） │
│ • 快速查找插入点 │
│ │
│ 5. 生活类比 │
│ ───────────────────────────────────────────── │
│ heapq = 医院急诊排队 │
│ • 病人按严重程度排序 │
│ • 最紧急的总是第一个被处理 │
│ • 新病人来了不用重新排全队 │
│ │
│ bisect = 字典翻页 │
│ • 字典按字母顺序排序 │
│ • 找单词时二分翻页定位 │
│ • 不需要从头翻到尾 │
│ │
└─────────────────────────────────────────────────────────────┘L1 理解层：会用
heapq: 堆队列算法
语法结构
┌─────────────────────────────────────────────────────────────┐
│ heapq 核心语法 │
│ │
│ 建堆： │
│ heapq.heapify(list) # 原地将列表转为堆 │
│ │
│ 入堆/出堆： │
│ heapq.heappush(heap, item) # 插入元素，O(log n) │
│ heapq.heappop(heap) # 弹出最小值，O(log n) │
│ heapq.heappushpop(heap, item) # 先入后出，更高效 │
│ heapq.heapreplace(heap, item) # 先出后入，更高效 │
│ │
│ Top K： │
│ heapq.nlargest(n, iterable, key) # 最大的 n 个 │
│ heapq.nsmallest(n, iterable, key) # 最小的 n 个 │
│ │
│ 参数说明： │
│ heap → 堆列表（已 heapify） │
│ item → 要插入的元素 │
│ n → 返回数量 │
│ iterable → 可迭代对象 │
│ key → 比较函数（可选） │
│ │
└─────────────────────────────────────────────────────────────┘最简示例：建堆与基本操作
python
import heapq
data = [5, 1, 9, 3, 7]
heapq.heapify(data)
print(f"堆顶（最小值）: {data[0]}") # 1
heapq.heappush(data, 0)
print(f"新堆顶: {data[0]}") # 0
smallest = heapq.heappop(data)
print(f"弹出最小值: {smallest}") # 0
print(f"堆顶: {data[0]}") # 1详细示例：Top K 问题
python
import heapq
nums = [12, 45, 2, 89, 33, 5]
print(f"最大的 3 个: {heapq.nlargest(3, nums)}") # [89, 45, 33]
print(f"最小的 3 个: {heapq.nsmallest(3, nums)}") # [2, 5, 12]
products = [
{"name": "A", "price": 10},
{"name": "B", "price": 50},
{"name": "C", "price": 30},
]
top_expensive = heapq.nlargest(2, products, key=lambda p: p["price"])
print(f"最贵的 2 个: {top_expensive}") # [{'name': 'B', 'price': 50}, {'name': 'C', 'price': 30}]关键代码说明
| 代码片段 | 含义 | 为什么这样写 |
|---|---|---|
heapq.heapify(data) | 原地将列表转为堆 | 建堆 O(n)，比逐个 heappush 更快 |
data[0] | 直接访问堆顶 | 小顶堆保证堆顶是最小值 |
heapq.heappush(heap, item) | 插入元素 | O(log n)，自动维护堆性质 |
heapq.heappop(heap) | 弹出最小值 | O(log n)，堆顶弹出后自动调整 |
heapq.nlargest(n, nums) | 获取最大的 n 个 | O(n log k)，比 sorted 更高效 |
bisect: 二分查找算法
语法结构
┌─────────────────────────────────────────────────────────────┐
│ bisect 核心语法 │
│ │
│ 查找插入位置： │
│ bisect.bisect_left(a, x) # 返回插入点左侧索引 │
│ bisect.bisect_right(a, x) # 返回插入点右侧索引 │
│ bisect.bisect(a, x) # 同 bisect_right │
│ │
│ 有序插入： │
│ bisect.insort_left(a, x) # 插入到左侧，保持有序 │
│ bisect.insort_right(a, x) # 插入到右侧，保持有序 │
│ bisect.insort(a, x) # 同 insort_right │
│ │
│ 参数说明： │
│ a → 已排序列表（必须排序！） │
│ x → 要查找/插入的元素 │
│ lo/hi → 搜索范围（可选） │
│ │
│ 区别： │
│ bisect_left: 相等元素插入左侧（找到第一个） │
│ bisect_right: 相等元素插入右侧（找到最后一个） │
│ │
└─────────────────────────────────────────────────────────────┘最简示例：查找插入位置
python
import bisect
scores = [10, 20, 30, 40]
pos_left = bisect.bisect_left(scores, 25)
print(f"bisect_left(25): {pos_left}") # 2
pos_right = bisect.bisect_right(scores, 20)
print(f"bisect_right(20): {pos_right}") # 2
bisect.insort(scores, 25)
print(f"插入后: {scores}") # [10, 20, 25, 30, 40]详细示例：分数定级系统
python
import bisect
def grade(score: int) -> str:
breakpoints = [60, 70, 80, 90]
grades = 'FDCBA'
index = bisect.bisect_right(breakpoints, score)
return grades[index]
for s in [55, 65, 75, 85, 95]:
print(f"分数 {s}: 等级 {grade(s)}")运行结果：
分数 55: 等级 F
分数 65: 等级 D
分数 75: 等级 C
分数 85: 等级 B
分数 95: 等级 A关键代码说明
| 代码片段 | 含义 | 为什么这样写 |
|---|---|---|
bisect.bisect_left(a, x) | 查找左侧插入位置 | 找到第一个 ≥ x 的位置 |
bisect.bisect_right(a, x) | 查找右侧插入位置 | 找到第一个 > x 的位置 |
bisect.insort(a, x) | 有序插入 | 插入并保持列表有序 |
bisect_right(breakpoints, score) | 区间映射 | 用于分数定级等区间场景 |
L2 实践层：用好
heapq 推荐做法
| 做法 | 原因 | 示例 |
|---|---|---|
| 频繁获取极值用 heapq | 堆顶访问 O(1) | heap[0] |
| 优先级队列用 heapq | 插入/弹出都是 O(log n) | heappush/heappop |
| Top K 用 nlargest/nsmallest | 比 sorted()[:k] 更高效 | nlargest(3, nums) |
| 批量建堆用 heapify | O(n) 比逐个插入快 | heapify(existing_list) |
heapq 反模式
python
import heapq
heap = []
for item in [5, 1, 9, 3, 7]:
heapq.heappush(heap, item)
print(heap)
print(heap.sort())
# 问题：
# 1. 堆不是完全有序列表，只是保证堆顶最小
# 2. sort() 会破坏堆结构
# 3. 不要期望 heap 是排好序的python
import heapq
data = [5, 1, 9, 3, 7]
heapq.heapify(data)
print(f"堆: {data}")
print(f"最小值: {data[0]}")
# 如果需要完全排序，用 sorted
print(f"排序结果: {sorted(data)}")python
import heapq
heap = [5, 1, 9, 3, 7]
heapq.heapify(heap)
smallest = heapq.heappop(heap)
heap.append(0)
print(f"堆顶: {heap[0]}")
# 问题：
# 1. append 后没有维护堆结构
# 2. heap[0] 可能不是最小值了python
import heapq
heap = [5, 1, 9, 3, 7]
heapq.heapify(heap)
smallest = heapq.heappop(heap)
heapq.heappush(heap, 0)
print(f"堆顶: {heap[0]}")
# 或用更高效的方式
heapq.heappushpop(heap, 0)heapq 实战：优先级任务队列
python
import heapq
from dataclasses import dataclass, field
@dataclass(order=True)
class Task:
priority: int
name: str = field(compare=False)
data: str = field(compare=False)
queue: list[Task] = []
tasks = [
Task(2, "发邮件", "Hello"),
Task(5, "备份数据库", "DB Backup"),
Task(1, "紧急修复", "Bug Fix"),
Task(3, "生成报表", "Report"),
]
for t in tasks:
heapq.heappush(queue, t)
while queue:
task = heapq.heappop(queue)
print(f"执行: {task.name} (优先级: {task.priority})")运行结果：
执行: 紧急修复 (优先级: 1)
执行: 发邮件 (优先级: 2)
执行: 生成报表 (优先级: 3)
执行: 备份数据库 (优先级: 5)关键代码说明：
| 代码 | 含义 | 为什么这样写 |
|---|---|---|
@dataclass(order=True) | 自动生成比较方法 | order=True 生成 __lt__，让 heapq 能比较 Task |
name: str = field(compare=False) | name 不参与比较 | 优先级只由 priority 决定 |
heapq.heappush(queue, t) | 插入堆 | O(log n) 比插入后 sort() 快 |
heapq.heappop(queue) | 弹出优先级最高 | 小顶堆 pop 返回最小值 |
heapq 适用场景
| 场景 | 是否推荐 heapq | 原因 |
|---|---|---|
| 优先级队列 | ✅ 推荐 | 核心场景，高效维护 |
| Top K 问题 | ✅ 推荐 | nlargest/nsmallest 高效 |
| 任务调度 | ✅ 推荐 | 实时获取优先任务 |
| 需要完全排序 | ❌ 不推荐 | 用 sorted() |
| 随机访问 | ❌ 不推荐 | 堆不支持高效随机访问 |
bisect 推荐做法
| 做法 | 原因 | 示例 |
|---|---|---|
| 列表必须先排序 | bisect 假设有序 | bisect.bisect(sorted_list, x) |
| 区间映射用 bisect_right | 符合区间边界习惯 | grade(score) |
| 避免频繁 insort | 列表插入仍是 O(n) | 批量操作用 extend + sort |
| 查找重复元素用 left/right 区分 | 精确定位第一个或最后一个 | bisect_left(arr, x) |
bisect 反模式
python
import bisect
scores = [30, 10, 40, 20] # 未排序！
pos = bisect.bisect(scores, 25)
print(f"插入位置: {pos}")
# 问题：
# 1. bisect 假设列表已排序
# 2. 未排序列表结果无意义
# 3. 可能返回错误位置python
import bisect
scores = [10, 20, 30, 40]
pos = bisect.bisect(scores, 25)
print(f"插入位置: {pos}") # 2
bisect.insort(scores, 25)
print(f"插入后: {scores}")python
import bisect
scores = [10, 20, 20, 20, 30]
pos_left = bisect.bisect_left(scores, 20)
pos_right = bisect.bisect_right(scores, 20)
print(f"第一个 20 的位置: {pos_left}") # 1
print(f"最后一个 20 后的位置: {pos_right}") # 4
# 查找所有 20
all_20 = scores[pos_left:pos_right]
print(f"所有 20: {all_20}") # [20, 20, 20]bisect 实战：价格区间分类
python
import bisect
def classify_price(price: float) -> str:
ranges = [0, 100, 500, 1000, 5000]
labels = ['免费', '便宜', '中等', '较贵', '昂贵']
index = bisect.bisect_right(ranges, price) - 1
return labels[index] if index >= 0 else '超出范围'
for p in [0, 50, 200, 800, 2000, 10000]:
print(f"价格 {p}: {classify_price(p)}")运行结果：
价格 0: 免费
价格 50: 便宜
价格 200: 中等
价格 800: 较贵
价格 2000: 较贵
价格 10000: 超出范围bisect 适用场景
| 场景 | 是否推荐 bisect | 原因 |
|---|---|---|
| 维护有序列表 | ✅ 推荐 | 减少全排序次数 |
| 区间映射 | ✅ 推荐 | 分数定级、价格区间 |
| 查找插入位置 | ✅ 推荐 | O(log n) 查找 |
| 频繁插入删除 | ❌ 不推荐 | 列表操作仍是 O(n) |
| 未排序列表 | ❌ 不推荐 | 结果无意义 |
L3 专家层：深入
heapq 原理
底层实现
┌─────────────────────────────────────────────────────────────┐
│ heapq 内部实现 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 小顶堆结构 │
│ ───────────────────────────────────────────── │
│ heapq 实现小顶堆（Min-Heap）： │
│ • 堆顶（索引 0）永远是最小值 │
│ • 父节点 ≤ 子节点 │
│ • 用列表模拟完全二叉树 │
│ │
│ 2. 索引关系 │
│ ───────────────────────────────────────────── │
│ 对于节点 i： │
│ • 父节点：(i - 1) // 2 │
│ • 左子节点：2 * i + 1 │
│ • 右子节点：2 * i + 2 │
│ │
│ 3. 堆可视化示例 │
│ ───────────────────────────────────────────── │
│ 堆 [0, 1, 5, 3, 7, 9] 的树结构： │
│ │
│ 0 (堆顶最小) │
│ / \ │
│ 1 5 │
│ /\ / │
│ 3 7 9 │
│ │
│ 列表存储：[0, 1, 5, 3, 7, 9] │
│ 不是完全排序，但堆顶保证最小 │
│ │
│ 4. 操作复杂度 │
│ ───────────────────────────────────────────── │
│ heapify: O(n) - 自底向上调整 │
│ heappush: O(log n) - 自顶向下调整 │
│ heappop: O(log n) - 弹出堆顶后调整 │
│ nlargest: O(n log k) - 使用堆排序 │
│ │
│ 5. 为什么 heapify 是 O(n) │
│ ───────────────────────────────────────────── │
│ • 自底向上调整，约一半节点无需调整 │
│ • 每层调整次数递减 │
│ • 数学证明：总次数 ≈ n │
│ │
└─────────────────────────────────────────────────────────────┘python
import heapq
data = [5, 1, 9, 3, 7]
print(f"原列表: {data}")
heapq.heapify(data)
print(f"堆列表: {data}")
def visualize_heap(heap: list[int]) -> None:
n = len(heap)
levels = 0
while (1 << levels) - 1 < n:
levels += 1
for level in range(levels):
start = (1 << level) - 1
end = min((1 << (level + 1)) - 1, n)
print(f" 层{level}: {heap[start:end]}")
visualize_heap(data)运行结果：
原列表: [5, 1, 9, 3, 7]
堆列表: [1, 3, 9, 5, 7]
层0: [1]
层1: [3, 9]
层2: [5, 7]heapq 性能考量
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
heapify(heap) | O(n) | 原地建堆，比逐个 heappush 快 |
heappush(heap, x) | O(log n) | 插入并调整堆 |
heappop(heap) | O(log n) | 弹出堆顶并调整 |
heap[0] | O(1) | 直接访问堆顶（最小值） |
nlargest(k, n) | O(n log k) | k 远小于 n 时高效 |
性能对比：
python
import heapq
import timeit
data = list(range(10000, 0, -1))
heap_time = timeit.timeit(
'heapq.nlargest(10, d)',
setup='import heapq; d = list(range(10000, 0, -1))',
number=100
)
sort_time = timeit.timeit(
'sorted(d)[:10]',
setup='d = list(range(10000, 0, -1))',
number=100
)
print(f"nlargest: {heap_time:.4f}s")
print(f"sorted[:10]: {sort_time:.4f}s")大顶堆实现
python
import heapq
class MaxHeap:
def __init__(self, data: list[int] | None = None) -> None:
self._heap: list[int] = []
if data:
self._heap = [-x for x in data]
heapq.heapify(self._heap)
def push(self, item: int) -> None:
heapq.heappush(self._heap, -item)
def pop(self) -> int:
return -heapq.heappop(self._heap)
def peek(self) -> int | None:
return -self._heap[0] if self._heap else None
def __len__(self) -> int:
return len(self._heap)
max_heap = MaxHeap([5, 1, 9, 3, 7])
print(f"堆顶（最大）: {max_heap.peek()}") # 9
print(f"弹出: {max_heap.pop()}") # 9
print(f"新堆顶: {max_heap.peek()}") # 7heapq 设计动机
| 设计选择 | 原因 |
|---|---|
| 小顶堆 | 符合优先级队列直觉（小优先级高） |
| 列表实现 | 无需额外数据结构，原地操作 |
| heapify O(n) | 批量建堆比逐个插入更快 |
| nlargest 用堆排序 | k 小时比全排序高效 |
heapq 知识关联
heapq 知识关联：
┌───────────────┐ ┌───────────────┐
│ list │────→│ heapq │
│ 动态数组 │ │ 堆队列 │
└───────────────┘ └───────────────┘
│
↓
┌───────────────┐
│ queue.Queue │
│ 线程安全队列│
└───────────────┘
│
↓
┌───────────────┐
│ PriorityQueue│
│ 优先级队列 │
└───────────────┘
│
↓
┌───────────────┐
│ sorted() │
│ 全排序 │
└───────────────┘bisect 原理
底层实现
┌─────────────────────────────────────────────────────────────┐
│ bisect 内部实现 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 二分查找算法 │
│ ───────────────────────────────────────────── │
│ bisect 使用二分查找（Binary Search）： │
│ • 每次比较排除一半元素 │
│ • 查找复杂度 O(log n) │
│ • Python 内部用 C 实现，极快 │
│ │
│ 2. 查找流程 │
│ ───────────────────────────────────────────── │
│ 目标：在有序列表 [10, 20, 30, 40] 查找 25 │
│ │
│ 步骤 1: 中点 = (0 + 4) // 2 = 2, 值 = 30 │
│ 25 < 30, 在左半部分继续 │
│ │
│ 步骤 2: 中点 = (0 + 2) // 2 = 1, 值 = 20 │
│ 25 > 20, 在右半部分继续 │
│ │
│ 步骤 3: 中点 = (2 + 2) // 2 = 2, 值 = 30 │
│ 找到插入位置 2 │
│ │
│ 3. bisect_left vs bisect_right │
│ ───────────────────────────────────────────── │
│ 对于相等元素： │
│ bisect_left: 返回第一个相等元素位置 │
│ bisect_right: 返回最后一个相等元素后的位置 │
│ │
│ 示例 [10, 20, 20, 20, 30]: │
│ bisect_left(..., 20) → 1（第一个 20） │
│ bisect_right(..., 20) → 4（最后一个 20 后） │
│ │
│ 4. insort 的复杂度 │
│ ───────────────────────────────────────────── │
│ • 查找位置：O(log n) │
│ • 列表插入：O(n)（移动元素） │
│ • 总复杂度：O(n) │
│ • 查找快，但插入仍慢 │
│ │
└─────────────────────────────────────────────────────────────┘python
import bisect
def binary_search_trace(arr: list[int], x: int) -> int:
lo, hi = 0, len(arr)
step = 0
while lo < hi:
mid = (lo + hi) // 2
step += 1
print(f"步骤 {step}: lo={lo}, mid={mid}, hi={hi}, arr[mid]={arr[mid]}")
if arr[mid] < x:
lo = mid + 1
else:
hi = mid
print(f"结果: {lo}")
return lo
arr = [10, 20, 30, 40, 50]
x = 35
print(f"数组: {arr}, 查找: {x}")
result = binary_search_trace(arr, x)
print(f"bisect_left 结果: {bisect.bisect_left(arr, x)}")运行结果：
数组: [10, 20, 30, 40, 50], 查找: 35
步骤 1: lo=0, mid=2, hi=5, arr[mid]=30
步骤 2: lo=3, mid=3, hi=5, arr[mid]=40
步骤 3: lo=3, mid=3, hi=3, arr[mid]=40
结果: 3
bisect_left 结果: 3bisect 性能考量
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
bisect_left/right(a, x) | O(log n) | 二分查找 |
insort_left/right(a, x) | O(n) | 查找 O(log n) + 列表插入 O(n) |
| 列表直接插入 | O(n) | 无查找优化 |
性能对比：
python
import bisect
import timeit
sorted_list = list(range(10000))
bisect_time = timeit.timeit(
'bisect.bisect(lst, 5000)',
setup='import bisect; lst = list(range(10000))',
number=10000
)
linear_time = timeit.timeit(
'for i, v in enumerate(lst): if v >= 5000: break',
setup='lst = list(range(10000))',
number=10000
)
print(f"bisect: {bisect_time:.4f}s")
print(f"线性查找: {linear_time:.4f}s")bisect 设计动机
| 设计选择 | 原因 |
|---|---|
| 二分查找 | O(log n) 比 O(n) 快得多 |
| 返回插入位置而非布尔 | 更灵活，支持 insort |
| left/right 区分 | 精确控制相等元素位置 |
| C 实现 | 性能优化 |
bisect 知识关联
bisect 知识关联：
┌───────────────┐ ┌───────────────┐
│ sorted list │────→│ bisect │
│ 有序列表 │ │ 二分查找 │
└───────────────┘ └───────────────┘
│
↓
┌───────────────┐
│ insort │
│ 有序插入 │
└───────────────┘
│
↓
┌───────────────┐
│ sorted() │
│ 全排序 │
└───────────────┘
│
↓
┌───────────────┐
│ list.sort() │
│ 原地排序 │
└───────────────┘本章小结
┌─────────────────────────────────────────────────────────────┐
│ heapq 与 bisect 核心功能回顾 │
├─────────────────────────────────────────────────────────────┤
│ │
│ heapq (堆): │
│ • heapify(list) - 原地建堆，O(n) │
│ • heappush/pop - 插入/弹出，O(log n) │
│ • nlargest/nsmallest - 高效获取 Top K │
│ • 堆顶 heap[0] - 直接访问最小值，O(1) │
│ │
│ bisect (二分): │
│ • 必须用于已排序列表！ │
│ • bisect_left/right - 查找插入点，O(log n) │
│ • insort_left/right - 有序插入，O(n) │
│ • 区间映射 - 分数定级、价格区间 │
│ │
│ 适用场景对比： │
│ • 找最大/最小值 → heapq │
│ • 维护优先级队列 → heapq │
│ • Top K 问题 → heapq │
│ • 动态维护有序列表 → bisect │
│ • 区间映射 → bisect │
│ │
└─────────────────────────────────────────────────────────────┘自检清单
回答以下问题，检查你是否掌握了核心概念：
heapq 是小顶堆还是大顶堆？如何获取堆顶元素？
答案：小顶堆。堆顶是最小值，通过
heap[0]直接访问（O(1)）。heapify 和逐个 heappush 建堆有什么区别？
答案：heapify 是 O(n)，逐个 heappush 是 O(n log n)。批量建堆用 heapify 更快。
bisect 为什么要求列表必须排序？
答案：二分查找基于有序假设，每次比较排除一半元素。未排序列表无法保证正确性。
bisect_left 和 bisect_right 有什么区别？
答案：相等元素时，bisect_left 返回第一个位置，bisect_right 返回最后一个位置后。
insort 的总复杂度是多少？为什么？
答案：O(n)。查找位置是 O(log n)，但列表插入需要移动元素，是 O(n)。
本章术语表
| 术语 | 定义 | 本章位置 |
|---|---|---|
| 堆 | 完全二叉树，堆顶是最值 | heapq L1 |
| 小顶堆 | 堆顶是最小值的堆 | heapq L1 |
| heapify | 原地将列表转为堆 | heapq L1 |
| heappush | 插入元素到堆 | heapq L1 |
| heappop | 弹出堆顶最小值 | heapq L1 |
| nlargest/nsmallest | 获取最大/最小的 n 个元素 | heapq L1 |
| 二分查找 | 每次排除一半元素的查找算法 | bisect L1 |
| bisect_left | 查找左侧插入位置 | bisect L1 |
| bisect_right | 查找右侧插入位置 | bisect L1 |
| insort | 有序插入元素 | bisect L1 |
| 区间映射 | 用 bisect 实现分数定级等 | bisect L2 |
扩展阅读
- Python 官方文档：heapq 模块
- Python 官方文档：bisect 模块
- 《算法导论》第6章：堆排序
- 《流畅的Python》第1章：数据结构选择