跳到主要内容

堆与优先队列

本节目标

用堆持续维护当前最重要的候选元素，掌握 Top K 与在线数据流问题的统一解法。

堆适合解决一类“只关心当前最值”的问题。它不会像有序数组那样维护所有元素的完整次序，而是用更低的维护成本，保证堆顶始终是当前最小值或最大值。

识别信号​

遇到下面这些描述时，可以优先考虑堆：

  • 从大量元素中寻找第 k 大、第 k 小或前 k 个元素；
  • 数据不断到来，每次加入后都要查询当前最值或第 k 大元素；
  • 同时存在多组有序数据，每次只需取所有组头部的最小候选；
  • 需要反复取出当前优先级最高的任务，并在过程中继续加入新任务。

关键词虽然常写成“最大”“最小”“前 K”，真正的判断标准却是：算法是否只需要保留一个规模有限的候选集合，并频繁访问其中的边界元素。

问题模型​

优先队列支持三种核心操作：

push(x)  把新候选加入集合
pop()    删除当前优先级最高的候选
top()    查看当前优先级最高的候选

这三种操作通常都是 O(log n) 或 O(1)：插入和删除需要调整堆，查看堆顶只需访问根节点。

“求第 k 大”最常用的模型是容量为 k 的小根堆：

  1. 新元素先进入堆；
  2. 若堆中超过 k 个元素，就删除最小值；
  3. 处理结束后，堆中恰好保留最大的 k 个元素；
  4. 其中最小的那个，也就是全局第 k 大元素。

这里看似要求“第 k 大”，却使用小根堆，因为堆顶承担的是“淘汰线”：比它更小的元素没有资格留在前 k 名中。

通用模板​

固定容量 Top K 模板：

创建小根堆 top
for x in 数据:
    把 x 加入 top
    if top 的大小 > k:
        删除 top 中的最小值
return top 的最小值

多路有序序列合并模板：

把每个非空序列的第一个元素加入小根堆
while 堆非空:
    取出全局最小候选 x
    把 x 接到答案末尾
    如果 x 所在序列还有后继:
        把后继加入堆

关键不变量是：堆里只放每一路尚未处理部分的第一个候选。这样既不会漏掉全局最小值，也不必把所有元素一次性装入堆。

母题序列​

  1. 数组中的第 K 个最大元素 必学
  2. 前 K 个高频元素 必学
  3. 数据流中的第 K 大元素 必学

建议按顺序完成：第一题建立固定容量小根堆模型；第二题先用哈希表提取统计信息，再用堆筛选候选；第三题把同一不变量迁移到持续到来的数据流中。

常见误区​

  • 最大问题就机械地使用大根堆：求第 k 大时，大根堆通常要保存全部元素；容量为 k 的小根堆更节省空间。
  • 把所有数据全部排序：排序当然可行，但如果只要前 k 个边界信息，往往维护小规模堆更贴合问题。
  • 忘记堆中保存的是什么：前 K 高频元素的堆应按“频率”比较，而不是按元素值比较。
  • 忽略相等优先级：对象无法直接比较时，需要明确次关键字，或加入唯一序号避免比较失败。
  • 只会离线处理：数据流题不能每次查询时重新排序全部历史数据，应让每次插入都恢复不变量。

迁移方向​

掌握这三道母题后，可以继续迁移到：

  • 合并多个有序序列：堆保存每一路当前的最小候选；
  • 数据流中位数：两个堆分别维护较小的一半和较大的一半；
  • 带优先级的图搜索：堆保存当前距离最小的待扩展状态；
  • 调度问题：堆保存当前最早结束、代价最低或优先级最高的任务。

迁移时先回答两个问题：堆中的一个元素代表什么候选？堆顶为什么一定是下一步应该处理或淘汰的元素？只要这两个问题清楚，代码通常只是对不变量的直接翻译。