Python 的 bisect 和 heapq 怎么用？分别解决什么问题？

简化版

bisect 和 heapq 是标准库里两个「用 C 实现的算法工具」，各自解决一类问题：bisect 处理「已排序列表上的二分查找与保序插入」，heapq 处理「反复取最小值」——也就是优先队列。bisect 的两个核心函数：bisect_left(a, x) 返回「x 应该插入的位置，使得它排在所有等于 x 的元素之前**」，bisect_right(a, x)（别名 bisect）返回「排在所有等于 x 的元素之后」的位置——查找是 O(log n)；再配 insort_left/right 做保序插入（注意插入本身是 O(n)，因为列表要搬移元素）。典型用途：按分数查等级、找最接近的值、统计区间内元素个数、维护有序列表。heapq 把普通 list 当成最小堆用：heappush(h, x)、heappop(h) 都是 O(log n)，heapify(lst) 原地建堆 O(n)，h[0] 就是最小值（O(1) 查看）；此外还有 nlargest/nsmallest（Top-K）和 merge（合并多个有序序列，惰性、省内存）。四个高频坑：① heapq 只有最小堆，要最大堆就存相反数或存 (-priority, item)；② 堆里放元组时是逐元素比较，第二个元素不可比较（如自定义对象）就会 TypeError，标准解法是加一个自增序号做第二关键字；③ bisect 要求列表已经有序，无序列表结果无意义且不报错；④ heap[1:] 不是「第二小的元素之后」——堆只保证 h[0] 最小，整体不是有序的。核心记忆：有序找位置用 bisect，反复取最小用 heapq；bisect 查 O(log n) 但插入 O(n)，heap 的 push/pop 都是 O(log n)。

详细版

两个模块的定位：

需求	用什么	复杂度
有序列表里查位置 / 判断存在	`bisect_left/right`	O(log n)
有序列表里保序插入	`insort_left/right`	查 O(log n) + 搬移 O(n)
反复取最小/最大值	`heapq`（堆）	push/pop 各 O(log n)，看堆顶 O(1)
一次性取 Top-K	`heapq.nlargest(k, it)`	O(n log k)
合并多个有序序列	`heapq.merge(*its)`	惰性、O(1) 附加内存
只需整体排序一次	`sorted()`	O(n log n)
频繁两端增删	`collections.deque`	两端 O(1)

import bisect, heapq

# ============ bisect ============
a = [10, 20, 20, 20, 30, 40]

# ① left / right 的区别（只有存在相等元素时才不同）
print(bisect.bisect_left(a, 20))    # 1  ← 排在所有 20 之前
print(bisect.bisect_right(a, 20))   # 4  ← 排在所有 20 之后
print(bisect.bisect_right(a, 25))   # 4  ← 不存在时两者相同
# 由此可得：等于 20 的元素个数 = right - left = 3

# ② 判断元素是否存在（比 in 快，O(log n) vs O(n)）
def contains(a, x):
    i = bisect.bisect_left(a, x)
    return i < len(a) and a[i] == x

# ③ 经典用法：分数 → 等级
grades = "FDCBA"
breakpoints = [60, 70, 80, 90]
def grade(score):
    return grades[bisect.bisect_right(breakpoints, score)]
print([grade(s) for s in (59, 60, 85, 100)])   # ['F', 'D', 'B', 'A']

# ④ 保序插入（★注意：插入是 O(n)★）
bisect.insort(a, 25)
print(a)                            # [10, 20, 20, 20, 25, 30, 40]

# ⑤ key 参数（Python 3.10+，之前只能自己拆成两个列表）
items = [("a", 1), ("b", 3), ("c", 7)]
print(bisect.bisect_left(items, 3, key=lambda t: t[1]))   # 1

# ============ heapq ============
# ⑥ 最小堆的基本操作（用普通 list 当堆）
h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, x)            # O(log n)
print(h[0])                         # 1  ← 堆顶永远是最小值，O(1)
print(heapq.heappop(h))             # 1  ← 弹出最小值，O(log n)
print(h)                            # [3, 5, 8]  ★不是有序列表，只保证 h[0] 最小★

nums = [9, 4, 7, 1]
heapq.heapify(nums)                 # ★O(n) 原地建堆，比逐个 push 的 O(n log n) 快★

# ⑦ 组合操作（比 pop+push 快，少一次调整）
heapq.heapreplace(h, 6)             # 先弹出最小、再压入（堆非空才行）
heapq.heappushpop(h, 0)             # 先压入、再弹出最小

# ⑧ 最大堆：存相反数
maxh = []
for x in [5, 1, 8]:
    heapq.heappush(maxh, -x)
print(-heapq.heappop(maxh))         # 8

# ⑨ 优先队列 + ★自增序号防止比较第二个元素★
import itertools
counter = itertools.count()
pq = []
class Task:                          # 自定义对象通常没有 __lt__
    def __init__(self, name): self.name = name
heapq.heappush(pq, (2, next(counter), Task("低优先级")))
heapq.heappush(pq, (1, next(counter), Task("高优先级")))
heapq.heappush(pq, (1, next(counter), Task("同优先级，先来先服务")))
prio, _, task = heapq.heappop(pq)
print(prio, task.name)              # 1 高优先级
# ★没有中间的序号时，两个优先级相同的元组会去比较 Task 对象 → TypeError

# ⑩ Top-K 和多路归并
data = [5, 1, 9, 3, 7]
print(heapq.nlargest(2, data))                    # [9, 7]
print(heapq.nsmallest(2, data, key=abs))          # [1, 3]
print(list(heapq.merge([1, 4], [2, 3], [5])))     # [1, 2, 3, 4, 5]（★惰性，可合并大文件★）

⚠️ 四个最容易错的点：① bisect 的前提是「列表已经有序」——无序列表上它照样返回一个数字，不报错但结果毫无意义，这类 bug 极难发现（尤其是列表在别处被 append 破坏了有序性时）。② insort 的插入是 O(n) 而不是 O(log n)：二分找位置确实是 O(log n)，但 Python 列表插入要把后面所有元素往后搬一格。所以「用 insort 维护一个百万级的有序列表并频繁插入」是反模式，该换成 SortedList（sortedcontainers 库，跳表实现）或改用堆。③ heapq 只有最小堆，要最大堆得存相反数（数值）或 (-priority, ...)（元组）。④ 堆不是有序列表：h[0] 保证是最小值，但 h[1]、h[2] 的顺序没有任何保证，直接 print(h) 看到的是堆的内部数组布局；要有序输出必须反复 heappop 或用 sorted(h)。

完整版教学

一、bisect：二分查找的两个方向

bisect_left(a, x)  返回插入点 i，使得 a[:i] 全 < x、a[i:] 全 >= x
bisect_right(a, x) 返回插入点 i，使得 a[:i] 全 <= x、a[i:] 全 > x
（bisect 是 bisect_right 的别名；insort 是 insort_right 的别名）

算例（a = [10, 20, 20, 20, 30]）：
  索引:      0    1    2    3    4
  值:       10   20   20   20   30
                 ↑              ↑
        left(20)=1        right(20)=4

  bisect_left(a, 20)  = 1     → 插在所有 20 的★前面★
  bisect_right(a, 20) = 4     → 插在所有 20 的★后面★
  bisect_left(a, 25)  = 4     ┐ 元素不存在时
  bisect_right(a, 25) = 4     ┘ 两者★相同★

由此推出三个实用公式：
  ① 等于 x 的元素个数     = bisect_right(a,x) - bisect_left(a,x)   （上例 4-1=3）
  ② x 是否存在            i = bisect_left(a,x); i < len(a) and a[i] == x
  ③ 区间 [lo, hi) 内的个数 = bisect_left(a,hi) - bisect_left(a,lo)

什么时候必须区分 left/right（面试爱问）：
  - 有重复元素且关心"插在前还是后"（稳定性）
  - 分级/分桶：分数正好等于边界值时算哪一档
    breakpoints = [60,70,80,90]
    bisect_right(bp, 60) = 1 → 60 分算 D（"≥60 及格"）
    bisect_left(bp, 60)  = 0 → 60 分算 F（"＞60 才及格"）
    ★ 边界语义完全靠选 left 还是 right 来表达★

其他参数：
  bisect_left(a, x, lo=0, hi=len(a))     限定搜索范围（避免切片复制）
  bisect_left(a, x, key=...)             ★Python 3.10+★，支持 key 提取比较字段
  ★ 3.10 之前想按 key 二分，只能预先建一个"只含 key 的平行列表"

bisect 的全部内容就是「插入点」这个概念：返回一个下标 i，把 x 插到这个位置后列表仍然有序。bisect_left 让 x 排在所有相等元素之前，bisect_right 排在之后——只有存在重复元素时两者才不同（不存在时返回值相同）。理解这一点后，三个高频用法都是直接推论：相等元素的个数 = right - left、判断存在性 = bisect_left 后检查该位置是否等于 x、区间计数 = 两个 bisect_left 相减。选 left 还是 right 不是随意的，它精确表达了边界语义：分数分级时用 bisect_right(breakpoints, 60) 表示「60 分及格」，用 bisect_left 则表示「超过 60 才及格」。另外记住两个参数：lo/hi 限定搜索范围（避免切片带来的复制），key= 是 Python 3.10 才加的（更早的版本只能维护一个「只含 key 的平行列表」）。

二、insort 的真实代价与选型

insort 做两件事：
  ① bisect 找位置        O(log n)   ← 很快
  ② list.insert(i, x)    ★O(n)★     ← 要把 i 之后的所有元素往后搬一格

所以维护有序列表的总代价：
  插入 n 个元素 = O(n²)（每次平均搬 n/2 个元素）

  数量级感受（Python 列表，粗略量级）：
    n = 1,000     insort 1000 次   → 毫秒级，随便用
    n = 100,000   insort 10 万次   → 秒级，开始难受
    n = 1,000,000 insort 100 万次  → ★分钟级★，不可接受

  ★ 但要公平地说：list.insert 的搬移是 C 层的 memmove，常数极小，
    所以在几千到几万的量级上，它往往仍然比"纯 Python 实现的平衡树"快。
    不要一看到 O(n) 就换轮子，先看数据规模。

四种"维护有序数据"的方案对比：
  ┌────────────────────┬──────────┬──────────┬────────────────────────┐
  │ 方案                │ 插入      │ 查询      │ 适用                    │
  ├────────────────────┼──────────┼──────────┼────────────────────────┤
  │ list + insort       │ O(n)     │ O(log n) │ ★n 不大 / 插入不频繁★   │
  │ 攒完一次 sorted()   │ —        │ O(log n) │ ★先全部收集再查询★（最优）│
  │ heapq               │ O(log n) │ 只能取最小│ 只关心最小/最大值        │
  │ SortedList(第三方)  │ O(√n)    │ O(log n) │ 大数据 + 频繁插入且要有序 │
  └────────────────────┴──────────┴──────────┴────────────────────────┘

选型决策：
  只需要"最后有序" → 全部 append 完再 sorted()（Timsort 极快，O(n log n) 一次搞定）
  边插边查、n 不大 → insort
  只关心极值      → heapq（★别用 insort 模拟优先队列★）
  n 大且要随机访问有序数据 → pip install sortedcontainers 的 SortedList

★ 经典反模式：用 insort 实现优先队列
  insort(q, task); q.pop(0)      ← 插入 O(n) + pop(0) 也是 O(n)
  ✓ 改用 heapq：push/pop 都是 O(log n)

insort 最容易被误解的地方是复杂度：二分找位置是 O(log n)，但插入本身是 O(n)——Python 的 list 是连续数组，插入要把后面的元素整体往后搬。所以「用 insort 维护一个百万级有序列表并频繁插入」是 O(n²) 的反模式。不过也要公平：list.insert 的搬移是 C 层的 memmove，常数极小，在几千到几万的规模上它常常比纯 Python 实现的平衡树还快，别一看到 O(n) 就急着换轮子。选型的关键是问清楚需求：只需要「最终有序」就全部 append 完再 sorted() 一次（Timsort 一次 O(n log n)，远优于边插边排）；只关心极值就用 heapq（用 insort + pop(0) 模拟优先队列是双重 O(n)，典型反模式）；确实需要「大数据 + 频繁插入 + 随机访问有序数据」，再上 sortedcontainers 的 SortedList。

三、heapq：堆是什么、为什么快

堆 = 用★数组★表示的完全二叉树，满足"父节点 ≤ 两个子节点"（最小堆）

  数组：      [1, 3, 8, 5, 4]
  对应的树：       1(0)
                 /    \
              3(1)    8(2)
              /  \
           5(3)  4(4)

  下标关系（heapq 的全部魔法就在这两行）：
    父 → 子：  left = 2*i + 1     right = 2*i + 2
    子 → 父：  parent = (i - 1) // 2

  ★ 关键性质：只保证"父 ≤ 子"，★兄弟之间没有顺序★
    所以 h[0] 一定是最小值，但 h[1] 不一定是第二小 → ★堆不是有序数组★

核心操作与复杂度：
  h[0]                O(1)       看最小值（不弹出）
  heappush(h, x)      O(log n)   放到末尾 → 不断和父节点比较、上浮
  heappop(h)          O(log n)   取走 h[0] → 把末尾元素放到堆顶 → 不断下沉
  heapify(lst)        ★O(n)★     原地建堆（不是 O(n log n)！）
  heapreplace(h, x)   O(log n)   先弹后压（比 pop+push 少一次调整）
  heappushpop(h, x)   O(log n)   先压后弹（如果 x 比堆顶小，直接返回 x）

★ heapify 为什么是 O(n) 而不是 O(n log n)：
  从最后一个非叶节点开始向前"下沉"，
  越靠近叶子的节点越多但下沉的距离越短，
  求和 Σ(层高 × 该层节点数) 收敛到 O(n)（而逐个 push 是 O(n log n)）
  → 已有一个列表要建堆，永远用 heapify，别循环 heappush

堆 vs 排序（该用哪个）：
  要全部有序          → sorted()，O(n log n)
  只要最小的 k 个     → heapq，O(n log k)  ★k 远小于 n 时优势巨大★
  数据流式到达、随时要当前最小 → heapq（sorted 每次都要重排）
  例：1000 万条日志里找最慢的 10 条
     sorted(data)[:10]        → 排全部 1000 万，内存也吃满
     heapq.nlargest(10, data) → 只维护 10 个元素的堆，★内存 O(k)★

heapq 把普通 list 当作用数组表示的完全二叉树来操作，全部魔法就在两行下标公式上（左子 = 2i+1、父 = (i-1)//2），不需要任何指针或节点对象——这正是它又快又省内存的原因。要牢牢记住堆的性质是「父 ≤ 子」而兄弟之间无序：所以 h[0] 必是最小值，但 h[1] 不一定是第二小，堆不是有序数组。复杂度方面有个常考点：heapify 是 O(n) 而不是 O(n log n)——它从最后一个非叶节点向前逐个下沉，越靠近叶子的节点数量越多但下沉距离越短，求和收敛到线性；所以已有列表要建堆时永远用 heapify，别循环 heappush。选择堆还是排序，关键看要不要「全部有序」：只要最小/最大的 k 个时，堆是 O(n log k) 且内存只有 O(k)——从一千万条日志里找最慢的 10 条，nlargest(10, data) 只维护 10 个元素，而 sorted(data)[:10] 要把全部数据排一遍还得全放内存。

四、优先队列：元组比较的坑与标准解法

最常见的用法：把 (优先级, 任务) 元组放进堆
  heappush(pq, (priority, task))
  → 弹出时按 priority 从小到大

★ 元组比较是"逐元素"的：先比第 0 个，相等再比第 1 个……
  (1, taskA) < (1, taskB)  → 第 0 个相等 → ★去比较 taskA < taskB★
  → 如果 task 是自定义对象且没有定义 __lt__：
    TypeError: '<' not supported between instances of 'Task' and 'Task'
  ★ 这个错误只在"优先级恰好相同"时才出现 → 测试环境不复现、线上偶发★

标准解法：插入一个★自增序号★作为第二关键字
  import itertools
  counter = itertools.count()
  heappush(pq, (priority, next(counter), task))
  → 优先级相同时比序号（永远不相等，且先入队的序号小）
  → 附赠一个好处：★同优先级下先进先出（稳定性）★

  取出：priority, _, task = heappop(pq)

其他解法：
  ② 给任务类定义 __lt__（或 @dataclass(order=True) 配 field(compare=False)）
     @dataclass(order=True)
     class Item:
         priority: int
         task: Any = field(compare=False)   # ★排除出比较★
  ③ 用 queue.PriorityQueue（线程安全版，内部就是 heapq），同样有元组比较问题

最大堆（heapq 只有最小堆）：
  数值：  heappush(h, -x)  ... -heappop(h)
  元组：  heappush(h, (-priority, seq, task))
  ★ 浮点数取负没有精度问题；但要注意 -0.0 和整数最小值这类边界

"删除堆中任意元素"的标准做法（懒删除）：
  堆不支持高效删除中间元素（O(n) 才能找到）
  ✓ 惰性删除：维护一个 removed 集合，弹出时跳过已删除的
    while pq:
        prio, seq, task = heappop(pq)
        if seq not in removed:
            return task
  ✓ 或标记法：把任务标记为 INVALID，弹出时判断
  （这是 heapq 官方文档推荐的模式，也是调度器的常见实现）

优先队列是 heapq 最主要的用途，而元组比较是这里唯一的大坑：Python 比较元组是逐元素进行的，(1, taskA) 和 (1, taskB) 第 0 个元素相等时会继续比较 taskA 和 taskB——自定义对象没有 __lt__ 就直接 TypeError。它的可怕之处在于只在优先级恰好相同时才触发，测试时往往不复现、线上偶发。标准解法是在中间插一个自增序号 next(itertools.count())：序号永不相等，保证比较到此为止，还附赠「同优先级下先进先出」的稳定性。另外两个选择是给任务类定义 __lt__，或用 @dataclass(order=True) 配 field(compare=False) 把 payload 排除出比较。最大堆靠存相反数实现（-x 或 (-priority, seq, task)）。最后记住堆不支持高效删除中间元素，官方推荐的做法是懒删除：维护一个已删除集合，弹出时跳过——这也是多数任务调度器的实现方式。

五、nlargest / nsmallest / merge：三个高层工具

① nlargest(k, iterable, key=None) / nsmallest(k, ...)
   heapq.nlargest(3, data)                       最大的 3 个（★降序返回★）
   heapq.nsmallest(3, data, key=lambda x: x.age) 支持 key
   复杂度 O(n log k)，内存 O(k)

   ★ 内部会按 k 和 n 的关系选策略：
     k == 1        → 直接 max()/min()（O(n)）
     k 接近 n      → 退化成 sorted()[:k]（此时堆没有优势）
     k << n        → 维护一个大小为 k 的堆   ← 优势区间

   选择准则：
     k == 1        → max()/min()
     k 很小、n 很大 → nlargest（★典型：千万日志找最慢 10 条★）
     k 接近 n / 之后还要全部有序 → sorted()

② merge(*iterables, key=None, reverse=False)
   把多个★已排序★的序列合并成一个有序序列，★惰性、内存 O(k)★（k=序列个数）
   list(heapq.merge([1,4,7], [2,3], [5,6]))    → [1,2,3,4,5,6,7]

   ★ 杀手级场景：外部排序（大到内存放不下的数据）
     1. 把 100GB 数据切成 100 份，每份排序后写成有序文件
     2. with ExitStack() as st:
            files = [st.enter_context(open(p)) for p in paths]
            for line in heapq.merge(*files):       # ★每个文件只在内存里留一行★
                out.write(line)
     → 内存占用 O(文件数)，而不是 O(数据量)

   ★ 前提：每个输入必须★已经有序★，否则输出是错的（不报错）

③ 组合技：用 merge + islice 取"多个有序流的前 N 个"
   from itertools import islice
   top = list(islice(heapq.merge(*sorted_streams), 100))
   → 只消费到第 100 个元素就停，后面的数据根本不读

★ 一个易忘的事实：nlargest/nsmallest 返回的是★列表★（已排好序），
  而 merge 返回的是★迭代器★（惰性、一次性）

这三个高层函数把堆的能力包装成了日常可用的形态。nlargest/nsmallest 是 Top-K 的标准答案，复杂度 O(n log k)、内存 O(k)——从一千万条记录里找最慢的 10 条，它只维护 10 个元素的堆，而 sorted()[:10] 要排全部数据；它内部还会根据 k 和 n 的关系自动选策略（k == 1 直接走 max()，k 接近 n 时退化成 sorted()），所以只在 k << n 时才有优势。merge 是多路归并，惰性且内存只有 O(序列个数)，它的杀手级场景是外部排序：把超出内存的数据切成多个有序文件，再用 merge(*files) 流式合并——每个文件在内存里只留一行。要注意它的前提是每个输入必须已经有序（否则输出错误且不报错），以及它返回的是迭代器（而 nlargest 返回列表），配合 islice 可以「只取前 N 个就停，后面的数据根本不读」。

六、选型总表与常见组合

按"需求"选工具：
  ┌──────────────────────────────┬────────────────────────────┐
  │ 需求                          │ 首选                        │
  ├──────────────────────────────┼────────────────────────────┤
  │ 一次性全部排序                 │ sorted() / list.sort()      │
  │ 有序列表里查位置/计数/判存在    │ bisect_left / bisect_right  │
  │ 有序列表里插入（n 不大）        │ insort                      │
  │ 反复取最小/最大                │ heapq                       │
  │ Top-K（k << n）               │ heapq.nlargest / nsmallest  │
  │ 合并多个有序流 / 外部排序       │ heapq.merge                 │
  │ 两端频繁增删                   │ collections.deque           │
  │ 大数据 + 频繁插入且要保持有序    │ sortedcontainers.SortedList │
  │ 线程安全的优先队列             │ queue.PriorityQueue         │
  └──────────────────────────────┴────────────────────────────┘

三个经典组合：
  ① 滑动窗口的中位数/分位数：
     用 bisect 维护一个有序的窗口列表（窗口不大时 insort 的 O(n) 可接受）
  ② 定时任务调度器：
     heap 里放 (触发时间戳, seq, callback)，
     主循环 sleep 到 h[0] 的时间 → pop → 执行 → 有周期的重新 push
     ★ 取消任务用懒删除（标记 + 弹出时跳过）
  ③ 合并排行榜 / 多路日志按时间归并：
     heapq.merge(*按时间排好序的流, key=lambda r: r.ts)

三条口诀：
  "有序找位置" → bisect（前提：★列表必须已排序★）
  "反复取极值" → heapq（只有最小堆，最大堆存相反数）
  "只要最终有序" → sorted() 一次搞定（别边插边排）

★ 复杂度速记：
  bisect 查 O(log n)、insort 插 O(n)
  heap  push/pop O(log n)、看堆顶 O(1)、heapify O(n)
  nlargest O(n log k)、merge 惰性 O(1) 附加内存

选型可以收敛成三句口诀：「有序找位置」用 bisect（前提是列表已排序）、「反复取极值」用 heapq（只有最小堆，最大堆存相反数）、「只要最终有序」直接 sorted() 一次搞定（别边插边排）。真实项目里最常见的三个组合是：用 bisect 维护滑动窗口的有序列表求中位数、用 heapq 存 (触发时间, seq, callback) 实现定时调度器（主循环 sleep 到 h[0] 的时间，取消任务用懒删除）、用 heapq.merge 做多路日志按时间归并。复杂度也要能张口就来：bisect 查 O(log n) 但 insort 插 O(n)；堆的 push/pop 各 O(log n)、看堆顶 O(1)、heapify 建堆 O(n)；nlargest 是 O(n log k)、merge 惰性且只占 O(1) 附加内存。

记忆钩子：「两个 C 实现的算法工具，各管一类问题：★bisect = 已排序列表上的二分查找与保序插入★，★heapq = 反复取最小值（优先队列）★。bisect 的核心是『插入点』：bisect_left 让 x 排在所有相等元素之前、bisect_right 排在之后（不存在时两者相同），由此推出三个公式——相等元素个数 = right - left、判存在 = bisect_left 后检查该位置、区间计数 = 两个 bisect_left 相减；分级时选 left 还是 right 精确表达了『≥ 还是 >』的边界语义；key= 参数是 3.10 才有的。★bisect 的两个前提/代价：列表必须已经有序（无序时不报错但结果无意义），insort 的插入是 O(n) 不是 O(log n)（list 要 memmove 搬元素）——所以『只要最终有序』就全部 append 完再 sorted() 一次。★heapq 是用数组表示的完全二叉树（父=(i-1)//2、子=2i+1/2i+2），只保证父≤子、兄弟无序，所以 h[0] 必是最小值但 h[1] 不一定是第二小——★堆不是有序数组★；push/pop 各 O(log n)、看堆顶 O(1)、heapify 建堆是 O(n)（比循环 push 的 O(n log n) 快，有现成列表就用它）。★四个高频坑：只有最小堆（最大堆存 -x 或 (-priority, …)）；元组比较是逐元素的，优先级相同时会去比较第二个元素，自定义对象没有 lt 就 TypeError（★只在优先级相同时偶发★），标准解法是插一个 itertools.count() 的自增序号（顺带实现同优先级 FIFO）；堆不能高效删除中间元素，用懒删除（标记 + 弹出时跳过）；nlargest/nsmallest 是 O(n log k)、内存 O(k)，只在 k << n 时才优于 sorted()[:k]。★heapq.merge 惰性合并多个已排序流、内存只有 O(流数)，是外部排序（数据大到放不下内存）的标准做法。」

七、常见误区与追问

误区：bisect.insort 是 O(log n) 的插入。 二分找位置是 O(log n)，但插入本身是 O(n)——Python 的 list 是连续内存数组，在中间插入必须把后面所有元素整体往后搬一格。所以用 insort 维护一个持续增长的有序列表，总代价是 O(n²)：一万个元素还好（毫秒级），一百万个就是分钟级。不过也别矫枉过正：list.insert 的搬移是 C 层的 memmove，常数极小，在几千到几万的规模上它往往仍比纯 Python 实现的平衡树快。判断标准是数据规模和插入频率：只需要「最终有序」就全部 append 完再 sorted() 一次；确实需要「大数据 + 频繁插入 + 保持有序」就上 sortedcontainers 的 SortedList。
误区：bisect 对任何列表都能用。 它的唯一前提是列表已经有序，而且无序时不会报错——照样返回一个看似合理的下标，只是结果毫无意义。这是最难查的一类 bug：初始化时列表是有序的，某处代码 append 了一个元素（或者按别的 key 排了序），从此所有 bisect 的结果都错了，却不抛任何异常，表现为「偶尔查错等级」「计数少了几个」。工程上的对策是：把「有序列表」封装进一个类，所有写入都走 insort（禁止裸 append）；或者在测试里加断言 assert a == sorted(a)；用 key= 参数时（3.10+）尤其要确认列表本身是按同一个 key 排序的。
误区：heapq 处理完的列表就是排好序的。 堆只保证「父节点 ≤ 子节点」，兄弟节点之间没有任何顺序——所以 h[0] 必定是最小值，但 h[1] 不一定是第二小，print(h) 打印出来的是堆的内部数组布局，看起来「大致有序」但并不是排序结果。想要有序输出只有两条路：反复 heappop（每次 O(log n)，全部弹完就是堆排序，总 O(n log n)）或者直接 sorted(h)。同理，h[1:] 不是「第二小及之后的元素」，h[-1] 也不是最大值（最大值一定在某个叶子上，但具体位置不确定，要 max(h) 才能拿到，O(n)）。
误区：把 (优先级, 对象) 放进堆就能用作优先队列。 只要出现两个优先级相同的元素，就会触发 TypeError——因为 Python 比较元组是逐元素的：第 0 个相等就去比较第 1 个，而自定义对象通常没有定义 __lt__。这个 bug 的阴险之处在于只在优先级恰好相同时才发作，开发和测试环境常常不复现，一到线上高并发就偶发。标准解法是在中间插一个自增序号：heappush(pq, (priority, next(counter), task))，itertools.count() 生成的序号永不重复，比较到这里必定分出胜负，还顺带实现了「同优先级先进先出」的稳定性。另外两个方案是给任务类定义 __lt__，或用 @dataclass(order=True) 配合 field(compare=False) 把 payload 排除出比较。
误区：heapq.nlargest(k, data) 永远比 sorted(data)[:k] 快。 只在 k 远小于 n 时才有优势。nlargest 是 O(n log k)、内存 O(k)，sorted()[:k] 是 O(n log n)、内存 O(n)——当 k 接近 n 时，前者的 log k 已经接近 log n，还多了维护堆的开销，反而更慢；实际上 CPython 的实现里 nlargest 会自己判断：k == 1 时直接调 max()，k 相对 n 足够大时干脆退化成 sorted()[:k]。选择准则是：k 为 1 用 max/min，k 很小而 n 很大用 nlargest（典型场景是一千万条日志找最慢的 10 条，内存只占 10 个元素），k 接近 n 或者之后还需要全部有序就直接 sorted()。
追问：heapify 为什么是 O(n) 而不是 O(n log n)？ 因为它不是「逐个插入」，而是从最后一个非叶节点开始向前，对每个节点做「下沉」操作。关键在于代价的分布：树里越靠近叶子的节点越多，但它们能下沉的距离越短——最底层约 n/2 个节点下沉距离为 0，倒数第二层约 n/4 个节点最多下沉 1 层，倒数第三层 n/8 个最多下沉 2 层……总代价是 Σ (n/2^(k+1)) × k，这个级数收敛到 2n，也就是 O(n)。而逐个 heappush 的话，每次插入都要从底部上浮，最坏 O(log n)，n 次就是 O(n log n)。结论：手上已经有一个列表要建堆时，永远用 heapify(lst)（还是原地的，不额外占内存），不要写 for x in lst: heappush(h, x)。
追问：怎么从堆里删除一个任意元素（比如取消一个已排队的任务）？ 堆不支持高效删除中间元素：要找到它就得 O(n) 线性扫描，删完还要重新调整。官方文档推荐的做法是懒删除（lazy deletion）：维护一个 removed 集合（或给任务对象加个 cancelled 标记），取消时只是把它记进集合、不动堆；弹出时循环跳过已被标记的元素，直到拿到一个有效任务为止。这样取消是 O(1)，弹出的均摊代价仍然很低。代价是堆里会残留「僵尸元素」占内存，所以通常配合一个阈值——当无效元素超过总数的一半时，重建一次堆（过滤掉无效元素后 heapify，O(n)）。绝大多数任务调度器（包括 asyncio 的定时器实现）用的都是这套模式。
追问：heapq.merge 和 sorted(chain(*iterables)) 有什么区别？ 结果一样（前提是每个输入都已排序），但资源特性完全不同。sorted(chain(*its)) 会把所有数据一次性读进内存建成一个列表再排序，内存 O(总数据量)、时间 O(N log N)，而且必须等全部数据到齐才能输出第一个元素。heapq.merge 是惰性的多路归并：它只在内存里维护「每个输入流的当前元素」（一个大小为「流个数」的小堆），内存 O(k)，每产出一个元素只需 O(log k)，而且边读边产出——可以配合 islice 只取前 100 个就停，后面的数据根本不读。这使它成为外部排序的标准工具：把 100GB 数据切成 100 个有序文件，再 heapq.merge(*files) 流式合并写出，内存占用只有文件数那么大。注意它的前提是每个输入必须已经有序（否则输出错误且不报错），以及它返回的是一次性的迭代器而不是列表。

八、加强记忆

bisect 和 heapq 是标准库里两个 C 实现的算法工具，分工明确：bisect 管「已排序列表上的二分查找与保序插入」，heapq 管「反复取最小值」（优先队列）。bisect 的核心概念是插入点：bisect_left 让 x 排在所有相等元素之前、bisect_right（别名 bisect）排在之后，元素不存在时两者相同。由此推出三个实用公式：相等元素个数 = right - left、判断存在 = bisect_left 后检查该位置的值、区间计数 = 两个 bisect_left 相减；分级场景里选 left 还是 right 精确表达了「≥」还是「>」的边界语义（key= 参数是 3.10 才加的）。它的两个前提与代价必须记牢：列表必须已经有序（无序时不报错但结果无意义，是极难查的 bug），insort 的插入是 O(n) 而非 O(log n)（list 要 memmove 搬元素）——所以「只要最终有序」就全部 append 完再 sorted() 一次，大数据加频繁插入才上 SortedList。heapq 是用数组表示的完全二叉树（父 (i-1)//2、子 2i+1/2i+2），只保证父 ≤ 子、兄弟之间无序，所以 h[0] 必是最小值但 h[1] 不一定是第二小——堆不是有序数组；push/pop 各 O(log n)、看堆顶 O(1)、heapify 建堆是 O(n)（越靠近叶子的节点越多但下沉越短，级数收敛到 2n），有现成列表时永远用它而不是循环 heappush。四个高频坑：① 只有最小堆，最大堆存相反数（-x 或 (-priority, ...)）；② 元组是逐元素比较的，优先级相同时会去比较第二个元素，自定义对象没有 __lt__ 就 TypeError（只在优先级相同时偶发），标准解法是插一个 itertools.count() 的自增序号（顺带实现同优先级 FIFO）；③ 堆不能高效删除中间元素，用懒删除（标记 + 弹出时跳过 + 超阈值重建）；④ nlargest/nsmallest 是 O(n log k)、内存 O(k)，只在 k << n 时才优于 sorted()[:k]（k=1 直接用 max/min）。最后，heapq.merge 惰性合并多个已排序流、附加内存只有 O(流个数)，是外部排序（数据大到放不下内存）的标准做法，配合 islice 还能「取够就停」。

简化版

详细版