priority-queue · binary heap

优先队列与二叉堆

优先队列（priority queue）是一种只关心「谁最该先出」的容器——不论入队顺序，每次都返回优先级最高 / key 最小的那个。它最主流的实现是二叉堆（binary heap）：一个用数组装着、却被当成完全二叉树看待的小结构，靠 sift-up / sift-down 两个「冒泡」动作在 $O(\log n)$ 内维持秩序。全文五节：朴素实现的代价 → 上浮与下沉 → 线性建堆与堆排序 → 堆作为算法零件 → 对顶堆与流式中位数。

1 · 朴素实现两端的代价

motivation · ADT 与朴素实现

优先队列先不谈实现，它只是一份契约（ADT），核心两个操作：

注 · ADT 的两个核心操作。insert(x) 放入一个带优先级的元素；extract-min() 取走并返回当前优先级最高的元素（本页约定 key 越小优先级越高）。另有 peek，只查看不取出。

用普通数组即可实现，但总有一端会变慢。图 1-1 让三种实现装同一批数，每执行一次 insert 或 extract-min 就累计各自的步数（一次比较判断或一次移动记一步），据此看出哪种实现在哪个操作上代价更高。

1.1 · 三种实现的代价

实现	insert	extract-min	一句话
无序数组	$O(1)$ （摊还）	$O(n)$	插入廉价，取最小需全表扫描
有序数组	$O(n)$	$O(1)$	取最小廉价，插入需移动大量元素
二叉堆	$O(\log n)$	$O(\log n)$	两端代价都不高

图 1-1 · 同一批数在无序数组、有序数组、二叉堆三种实现下的累计步数。可反复执行 insert 与 extract-min，观察两端代价的分化：无序数组的 extract 与有序数组的 insert 随规模线性增长，二叉堆两栏都只缓慢增长。

2 · 二叉堆的心脏：上浮与下沉

core · 单步插入 / 取最小

二叉堆是个完全二叉树：每一层从左到右填满，最后一层也尽量靠左。这种规整形状让它能压进一个数组，父子关系纯靠下标算术：

注 · 完全二叉树的下标算术与堆性质。下标 $i$ 的父子关系是 parent = (i - 1) >> 1、left = 2 * i + 1、right = 2 * i + 2。最小堆性质是每个节点的 key $\le$ 它两个孩子，于是根永远是全局最小。维持它只靠两个动作：新元素 sift-up 上浮、堆顶移走后由末尾元素 sift-down 下沉。两者各沿一条根——叶路径移动（上浮由下往上，下沉由上往下），路径长不超过树高 $\lfloor \log_2 n \rfloor$ ，所以是 $O(\log n)$ 。

图 2-1 · 单次 insert 的上浮与单次 extract-min 的下沉，数组与完全二叉树同步高亮。可改插入值并单步执行，右栏代码同步点亮当前行。

警示 · 空缺必须由末尾元素填补。extract-min 把末尾元素搬到根再下沉，而不是把根的某个孩子提上来，这样数组不会出现空洞。这是最省事的做法而非唯一做法：另有一类空穴变体，沿「较小孩子」的路径把孩子逐级提上来，空穴落到路径末端后再把原末尾元素填进去并上浮，形状同样保持完全二叉树，比较次数还更少（每层 1 次而非 2 次），代价是实现更绕。同理 insert 永远先放末尾再上浮。

3 · 线性建堆与堆排序

heapify · O(n) 建堆 + 堆排序

要把一组乱序数字变成堆，最朴素的办法是 $n$ 次 insert，每次 $O(\log n)$ ，最坏合计 $O(n \log n)$ 。heapify [2] 更快：从最后一个有孩子的节点往前，对每个节点做一次 sift-down，只要 $O(n)$ 。

注 · 自底向上使下沉高度的加权和收敛。做某个节点的 sift-down 时，它的两棵子树已经是堆了。靠近底部的节点极多，但它们能下沉的高度极小（叶子那层根本不用动）；只有少数靠近根的节点才可能沉很深。把「节点数 × 各自最大下沉高度」加总，级数收敛到 $O(n)$ 。实测随机输入的交换次数： $n = 1000$ 时 749 次、 $n = 4000$ 时 3005 次，都在 $0.75n$ 上下。

图 3-1 · 自底向上 heapify 的逐步过程，并对照逐个 insert 的交换次数。可改输入数组或点「打乱」，观察两种建堆方式在不同输入下的差距。

注 · 这个差距在小数组上常常看不见。原以为 $O(n)$ 与 $O(n\log n)$ 的分野在几个元素上就该显形，图 3-1 的红绿标记原本也是照这个前提硬编码的。实测推翻了：默认数组 9, 4, 7, 1, 8, 3, 6, 2, 5 上两者都是 6 次交换；把「打乱」按钮的 $n \in [6, 11]$ 跑 200 组，78 组完全打平，没有一组 heapify 更差。差距要到逆序输入才拉开—— $n = 4096$ 时 heapify 4085 次、逐个 insert 40974 次，十倍；随机输入下逐个 insert 的期望也是线性的，只多出约 1.7 倍常数。 $O(n\log n)$ 是最坏界，不是随机输入下的期望。改的是正文与图 3-1 的标记，不是引擎。

3.1 · 最小堆收集版

建好最小堆后反复 extract-min，取出的就是升序序列，这就是堆排序 heapsort [1]。

图 3-2 · 最小堆反复 extract-min 得到升序输出，输出写在额外数组里。可单步取值，观察堆一点点缩小、有序输出一点点变长。

警示 · 收集版需要额外 $O(n)$ 空间。它把每次取出的最小值追加进新数组 out，看着最直观，但严格说不是原地排序。只用数组本身的做法见 §3.2。

3.2 · 最大堆原地版

不开 out 的关键是改用最大堆（根即最大），把数组就地切成两段：前段是堆区，尾段是已锁定的排序区。每一步把堆顶最大值和堆区末尾交换，最大值就此落到它的最终位置、并入排序区；堆区长度减 1，新根再 sift-down 复原。重复到堆区只剩一个元素——它就是全局最小，已经在 a[0]，不必再动。数组于是原地升序。

图 3-3 · 最大堆原地堆排序，绿色边界是已锁定的排序区。可单步执行，观察边界自右向左推进。

建议 · 两版本质是同一块积木：建堆加上不断取最值。堆排序最坏 $O(n \log n)$ ，不像快排会退化到 $O(n^2)$ ，且 §3.2 那版还是原地的。代价是常数与缓存局部性都明显差于快排：实际库函数多用 introsort，快排打底、只在递归过深时切回堆排序。用最小堆收集得升序、用最大堆原地也得升序，方向只是对称选择。

4 · 堆作为算法内部零件

applications · 堆的实际应用

优先队列常常不以自己的名字出现，而是嵌在其他算法内部，负责「每次返回当前最该处理的那个」。最直接的用法是流式 Top-K：数据像水一样流过，内存里只留一个 size- $k$ 的堆，就能始终盯住目前最大的 $k$ 个。

注 · 留最大的 $k$ 个反而要用最小堆。堆顶是这 $k$ 个里最小的那个，也就是当前的阈值元素。新来一个数，只要它比堆顶大就移除堆顶、放它进来，否则直接丢弃。填充阶段过后堆里恒有 $k$ 个元素，内存与流长无关。代价上要注意主导情形：绝大多数元素走的是「不大于堆顶、直接丢弃」这一支，只花一次比较； $O(\log k)$ 只在换入时发生，随机流上换入概率约 $k/i$ ，所以总代价接近 $O(n)$ 而非 $O(n\log k)$ 。

图 4-1 · size-

k

最小堆维护流式 Top-K，堆顶即当前阈值。可改

k

并持续喂入数据，观察保留与丢弃的分界。

4.1 · 同一零件的不同外壳

把「每次取最该处理的那个」这件事抽出来，一大批经典算法里都能找到堆：

Dijkstra 最短路 →

堆里装「已知最短距离的边界点」，每次 extract-min 取出当前 dist 最小的点 settle，再把它的邻居按新距离重新压入堆（惰性插入，出堆时跳过已 settle 的点）。把主循环里的线性找最近点换成堆，复杂度由 $O(V^2)$ 变为 $O((V+E)\log V)$ ——稀疏图上是净赚，稠密图上朴素扫描反而更优。若要真正的 $O(\log n)$ decrease-key，二叉堆还得额外维护元素到下标的句柄表。

Prim 最小生成树 →

和 Dijkstra 几乎一个模子：堆里装「树到外部各点的最便宜连边」，每次取最小的那条边把新点并进树，再用它的邻边更新堆。

Huffman 建树 →

整个建树过程就是反复取两个最小：从堆里 extract-min 两次、合并成新节点、再 insert 回去，直到只剩一个。优先队列就是它的引擎。

合并 k 个有序序列

k 路归并：堆里放每条序列「当前最小的那个头」，每次 extract-min 输出全局最小，再从它所在序列补一个进来。外部排序、LSM-tree compaction、merge-sort 的多路版都靠它。

事件驱动模拟 / 定时器

离散事件模拟、游戏循环、OS 定时器队列：堆按「触发时间」排，主循环永远 extract-min 取下一个该发生的事件，处理时可能再 insert 新事件。

任务调度 / 带优先级的就绪队列

操作系统调度、打印队列、Web 请求限流：就绪任务按优先级入堆，CPU 空出来就 extract 优先级最高的去跑。这正是「priority queue」名字的由来。

对顶堆求「流式中位数」↓

两个堆背靠背：一个最大堆装较小的一半、一个最小堆装较大的一半，保持两边数量平衡，中位数只由两个堆顶决定。每来一个数 $O(\log n)$ 维护，见 §5。

建议 ·「当前最该处理哪一个」这个问法，多数时候由一个堆来回答。但不是全部：整数键有界时桶队列与 radix heap 能做到摊还 $O(1)$ ，滑动窗口最值用单调队列是 $O(1)$ ，键只增不减的事件流常用时间轮。堆的长处是对键的类型不作假设。

5 · 对顶堆与流式中位数

applications · 两个堆背靠背

数据像流一样进来，随时要问「到目前为止的中位数」。离线求中位数有 $O(n)$ 的选择算法，流式的难处在于每来一个数都要立刻给答案，重跑一次选择就是 $O(n)$ 。对顶堆把数分成两半，各用一个堆盯住分界处：最大堆 lo 装较小的一半（堆顶是较小半里最大的），最小堆 hi 装较大的一半（堆顶是较大半里最小的）。两条不变式同时成立时，中位数只由两个堆顶决定——其一，lo 里每个元素都不大于 hi 里每个元素；其二，两堆大小差不超过 1。只有第二条是不够的：lo = {5, 9}、hi = {1, 7} 大小相等，两顶给出 5，而真实中位数是 6。

注 · 插入与再平衡的规则。每来一个 x，先按「不大于 lo 顶就进 lo，否则进 hi」放好，这一步维持第一条不变式；再看哪边多了，把它的堆顶移一个给另一边，使 lo 的元素数比 hi 多 0 个或 1 个，这一步维持第二条。读中位数时，两堆等大取两个堆顶的平均，lo 多一个则直接取 lo 顶。插入与再平衡都只是 $O(\log n)$ 的堆操作。

图 5-1 · 对顶堆维护流式中位数，上为最大堆 lo、下为最小堆 hi。可持续插入，观察再平衡与中位数读数。

建议 · 两个堆顶之所以够用，是因为在两条不变式下 lo 顶是小半里最大、hi 顶是大半里最小，它们正好卡在整个数据集正中央的两侧，无需触碰堆里其余元素。同样的思路还能扩展到滑动窗口中位数、带删除的中位数（配合延迟删除）等变体。

注 · 这套堆正是 Huffman 建树反复「取两个最小」、Dijkstra 与 Prim 每次「取最近的边界点」时，底下那个真正在跑的数据结构。

注 · 二叉堆的 insert 是最坏 $O(\log n)$ ，但平均只要常数时间。对随机堆随机插入实测： $n = 1023$ 时平均 2.44 次上浮交换、 $n = 4095$ 时 2.23 次、 $n = 16383$ 时 2.13 次—— $n$ 翻 16 倍代价不增反降，与 Porter 和 Simon 给出的期望 $O(1)$ 结论 [3][4] 一致。作为对照，extract-min 的比较步数实测 10、11、13，确实随 $\log n$ 走。

还有一处实现上的坑：heapifySwapCount 内部走的是 heapifySteps，而后者每一步都快照整个数组，内存是 $\Theta(n \cdot \text{steps})$ 。 $n = 4000$ 尚可（12012 步）， $n = 10000$ 直接把 node 跑到 OOM。它只在 lab 的 $n \le 11$ 上使用，不能拿去量大数组。

6 · 参考文献

Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
Floyd, R. W. (1964). Algorithm 245: Treesort 3. Communications of the ACM, 7(12), 701.
Porter, T., & Simon, I. (1975). Random insertion into a priority queue structure. IEEE Transactions on Software Engineering, SE-1(3), 292–298.
Bollobás, B., & Simon, I. (1985). Repeated random insertion into a priority queue. Journal of Algorithms, 6(4), 466–477.