堆与优先队列
01 / 共享的机制
堆让你廉价地拿到极值 —— 最小或最大 —— 而其余元素保持松散的、半排序状态。三个子模式:一个堆做 Top-K,两个堆维护流式中位数, 一个由源指针构成的小顶堆合并 K 路有序流。
在上面选一个子模式。每个子模式都可以单独跳转 —— 从题目最像的那个开始。
↑ 选一个— / 什么时候用哪个
Top-K
当你只要最极端的 k 个而不是完整顺序时使用。
流式 · O(N log k) · LC 215 / 347 / 703
双堆
当你要在线维护中位数时使用 —— 用大顶堆装下半,小顶堆装上半。
中位数 · 大顶堆 + 小顶堆 · LC 295
合并 K 路
当有 K 个有序流,需要不断取出当前最小值时使用。
合并 · (val, src, idx) · LC 23 / 378