priority-queue · binary heap

优先队列 · 拆解 priority queue & binary heap

优先队列(priority queue)是一种只关心「谁最该先出」的容器——不论入队顺序，每次都返回优先级最高 / key 最小的那个。它最主流的实现是 二叉堆(binary heap)：一个用数组装着、却被当成完全二叉树看待的小结构，靠 sift-up / sift-down 两个「冒泡」动作在 $O(\log n)$ 内维持秩序。每个 demo 都能改输入、点单步，看数组与树同步变化，旁边的代码面板高亮当前执行行。全文四步：为什么需要堆 → 上浮与下沉 → 建堆与堆排序 → 堆的实际应用。

1 · 为什么需要堆：朴素做法贵在哪

motivation · ADT 与朴素实现

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

insert(x)——放入一个带优先级的元素。

extract-min()——取走并返回当前优先级最高的元素（本系列约定 key 越小优先级越高）。

（另有 peek，只查看不取出。）

用普通数组即可实现——但总有一端会变慢。下面三栏装着同一批数，每点击一次 insert / extract-min，三种实现各自执行一遍，实时累计它们消耗的「基本操作数」（比较 + 移动），从而看出哪种实现在哪个操作上代价更高。

1.1 · 三种实现的代价

实现	insert	extract-min	一句话
无序数组	O(1)	O(n)	插入廉价，取最小需全表扫描
有序数组	O(n)	O(1)	取最小廉价，插入需移动大量元素
二叉堆	O(log n)	O(log n)	两端代价都不高——这正是堆的优势所在

多执行几次 insert 和 extract-min：无序数组的 extract、有序数组的 insert 会随规模线性增长，而二叉堆两栏都只缓慢增长。下面二叉堆的上浮与下沉剖析这台「两端都低开销」的结构。

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

core · 单步插入 / 取最小

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

下标 i 的 parent = (i-1)>>1、left = 2i+1、right = 2i+2。

**（最小）堆性质：**每个节点的 key ≤ 它两个孩子 → 根永远是全局最小。维持它只靠两个动作：新元素 sift-up 上浮、堆顶移走后空缺由末尾元素 sift-down 下沉，各走一条根到叶的路径，所以是 $O(\log n)$ 。

下面输入一个值 insert、或点 extract-min 取走堆顶，然后反复点「下一步」看数组与树同步地比较 / 交换，右侧代码逐行点亮。

注意：extract-min 把末尾元素搬到根再下沉，而不是把根的某个孩子提上来——这样才能始终保持「完全二叉树」形状（数组无空洞）。同理 insert 永远先放末尾再上浮。

3 · 一次建好整堆：为什么是 O(n)，以及堆排序

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

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

为什么更快？关键在从下往上：做某个节点的 sift-down 时，它的两棵子树已经是堆了。靠近底部的节点极多，但它们能下沉的高度极小（叶子那层根本不用动）；只有少数靠近根的节点才可能沉很深。把「节点数 × 各自最大下沉高度」加总，级数收敛到 $O(n)$ 。

3.1 · 用堆做排序其一：最小堆 + 收集（最直观）

建好最小堆后，反复 extract-min 取出的就是升序序列——这就是堆排序 heapsort。点「取下一个」看堆一点点缩小、有序输出一点点变长。注意: 这一版把取出的值追加进一个新数组 out，看着最直观，但它要额外 $O(n)$ 空间——严格说不是原地排序。真正原地的版本见下面「最大堆 + 换到末尾」一节。

这版不是原地的。为了直观，上面把每次取出的最小值追加进了新数组 out，额外占 $O(n)$ 空间。要做到只用数组本身，得换个思路——见下面「最大堆 + 换到末尾」一节。

3.2 · 用堆做排序其二：最大堆 + 换到末尾（原地）

不开 out 的关键：改用最大堆（根 = 最大），把数组就地切成两段——前段是堆区，尾段是已锁定的排序区（浅绿）。每一步把堆顶最大值和堆区末尾交换，最大值就此落到它的最终位置、并入排序区；堆区长度 $-1$ ，新根再 sift-down 复原。重复到堆区为空，数组自然原地升序。点「下一步」看那条绿色边界从右往左长出来。

两版本质是同一块积木：建堆 + 不断取最值。堆排序最坏 $O(n \log n)$ ——不像快排会退化到 $O(n^2)$ ；而「最大堆 + 换到末尾」这版还做到了原地（只用数组本身）。用最小堆收集得升序、用最大堆原地也得升序，方向只是对称选择。

4 · 应用实例：堆藏在哪些算法里

applications · 堆的实际应用

优先队列几乎不单独出现，它总是作为其他算法的内部零件，负责「每次返回当前最该处理的那个」。先看一个最直接的用法：流式 Top-K——数据像水一样流过，内存里只留一个 size-k 的堆，就能始终盯住「目前最大的 k 个」。

关键：要留最大的 k 个，反而用最小堆。堆顶 = 这 k 个里最小的那个，也就是当前的阈值元素。新来一个数，只要它比堆顶大，就移除堆顶、放它进来；否则直接丢弃。堆永远只有 k 个元素，每来一个数只花 $O(\log k)$ ——哪怕数据流是十亿条、内存只装得下 k 个。

4.1 · 同一个零件，不同外壳

把「每次取最该处理的那个」这件事抽出来，你会在一大批经典算法里反复看到堆：

Dijkstra 最短路 →

堆里装「已知最短距离的边界点」，每次 extract-min 取出当前 dist 最小的点 settle，再把它的邻居 decrease-key / 插入。把主循环里的「线性找最近点」换成堆，复杂度从 $O(V^2)$ 降到 $O(E \log V)$ 。

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)$ 维护。下面有可交互 lab。

理解这一点，一大类数据结构问题就有了统一答案：「当前最该处理哪一个？」几乎总是由一个堆来回答。

5 · 对顶堆：O(log n) 维护流式中位数

applications · 两个堆背靠背

数据像流一样进来，随时要问「到目前为止的中位数」。排序求中位是 $O(n \log n)$ 且每来一个就得重排。对顶堆把数分成两半各用一个堆盯住分界处：一个最大堆 lo 装较小的一半（堆顶 = 较小半里最大的），一个最小堆 hi 装较大的一半（堆顶 = 较大半里最小的）。只要两堆大小差 ≤ 1，中位数就夹在两个堆顶之间。

每来一个 x：先按「比 lo 顶小就进 lo，否则进 hi」放好，再再平衡——哪边多了就把它的堆顶移一个给另一边，使 ${0 \le |lo| - |hi| \le 1}$ 。读中位数：两堆等大取两个堆顶的平均；lo 多一个则直接取 lo 顶。插入与再平衡都只是 $O(\log n)$ 的堆操作。

为什么两个堆顶就够。 lo 顶是「小半里最大」、hi 顶是「大半里最小」——它们正好卡在整个数据集的正中央两侧。只要维持两堆几乎等大，中位数永远只看这两个数，无需触碰堆里其余元素。同样的「两个堆夹一条线」思路还能扩展到滑动窗口中位数、带删除的中位数（配合「延迟删除」）等变体。

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