pos 数组 · decrease-key · 惰性删除

索引堆与 decrease-key

Dijkstra 的教科书复杂度写作 $O((V + E) \log V)$ ，推导只用到一条假设：每次松弛成功时，把某个已在队列里的顶点的 key 调小，代价 $O(\log V)$ 。这个操作叫 decrease-key。

二叉堆给不出这个代价。改 key 之后让它上浮不难，那正是 push 的后半段；难的是上浮之前的一步：这个元素现在落在数组的哪一格。

1 · 堆丢掉的那半份映射

堆数组只记录一个方向的对应：下标 $i$ 上放着哪个元素。反过来问「元素 $x$ 在哪个下标」，数组没有答案。

push 与 pop 都不需要这半份映射。push 从末尾开始上浮，pop 从根开始下沉，起点都是常数位置。只有 decrease-key 的起点是任意元素，于是它卡在这一步上。

没有额外结构时唯一的补救是扫描：遍历整个数组找到那个元素， $O(n)$ 。一次线性扫描加一次对数上浮，decrease-key 的复杂度由后者主导变成由前者主导；Dijkstra 里 decrease-key 至多做 $E$ 次，总代价从 $O(E \log V)$ 退化到 $O(EV)$ 。稠密图上这是两个数量级的差别。

2 · pos 数组

定义 2.1（pos 数组） 设堆内共 $n$ 个元素，heap[i] 是第 $i$ 格上元素的编号。索引堆额外维护数组 pos，满足 $\mathrm{pos}[\mathrm{heap}[i]] = i$ 对一切 $0 \le i < n$ 成立；不在堆内的编号取 $-1$ 。换言之 pos 是 heap 的反函数。

图 2-1 · 索引堆的单步操作：上排是堆数组，下排是 pos 数组。可选一个元素调小它的 key，观察上浮路径与 pos 的同步改写，或直接 extractMin 看 pos 置 −1。

维护规则只有一条：凡是写 heap 的地方，同步写 pos。核心是交换那一句，从写两个格子变成写四个：

$\mathrm{heap}[i] \leftrightarrow \mathrm{heap}[j], \quad \mathrm{pos}[\mathrm{heap}[i]] = i, \quad \mathrm{pos}[\mathrm{heap}[j]] = j$

有了它，三个操作各就各位。contains(x) 是一次 $\mathrm{pos}[x] \ge 0$ 的判断；decreaseKey(x, k) 先由 pos 定位再上浮， $O(\log n)$ ；extractMin 在摘掉根时把它的 pos 置 $-1$ 。空间代价是一个长度为编号上界的整数数组，时间代价是每次交换多两次写入。

调大 key 不能走同一条路：那要下沉而不是上浮，且下沉不保证元素仍在原子树内。索引堆的实现一般直接拒绝调大的请求，需要时用 increase-key 单独写一份。

3 · 教科书复杂度的前提

有了 decrease-key，Dijkstra 的操作次数才能逐项数清：每个顶点至多进堆一次，堆内元素永不超过 $V$ ，extract-min 恰好 $V$ 次；每条边至多触发一次松弛成功，decrease-key 至多 $E$ 次。两项各付 $O(\log V)$ ，合成 $O((V + E) \log V)$ 。Prim 的最小生成树同构，只是把 key 从「源点距离」换成「到已选集合的最短边权」。

实测一张 $V = 200$ 、 $E = 799$ 的随机连通图：入堆 200 次（恰好等于 $V$ ），decrease-key 136 次，出堆 200 次，堆内峰值 132。没有一条过期条目需要丢弃，因为堆里从来只有每个顶点的当前最优值。

4 · 惰性删除与过期条目

工程代码里更常见的是另一种写法：完全不做 decrease-key。松弛成功时把 (新距离, 顶点) 当作一条新记录直接入堆，出堆时检查该记录的距离是否仍等于当前已知的 dist，不等就丢弃。

图 4-1 · 同一张图上两种 priority queue 的操作计数。表格逐项对照入堆、出堆、过期丢弃、堆峰值与总比较次数，下方两栏是堆峰值与比较次数的柱状对照。可换顶点数与边密度。

同一张 $V = 200$ 、 $E = 799$ 的图上，惰性写法入堆 335 次、出堆 335 次、其中 135 条是过期记录，堆内峰值 204，总比较 4383 次。与索引堆的 2493 次相比是 1.76 倍，堆峰值是 1.55 倍。两者算出的 dist 数组逐项相同。

倍率随边密度张开： $E \approx 2V$ 时 1.30 倍， $E \approx 4V$ 时 1.77 倍， $E \approx 10V$ 时 2.31 倍。原因直白，重复入堆的条数与松弛成功的次数同阶，而后者随 $E$ 增长，索引堆的 $V$ 条上限却不随 $E$ 变。

惰性写法的收益全在实现侧：它不要求底层结构支持按元素定位，任何一个只有 push 与 pop 的 priority queue 都能用，标准库自带的那个就行。多付的是常数倍的比较与内存。

注 · 一条被实测推翻的等式。原本以为惰性版本的入堆次数恒等于索引版的「入堆 + decrease-key」之和，因为两边的触发条件同是「松弛成功」。实测不等： $V = 200$ 、 $E = 799$ 上是 335 对 336， $V = 800$ 、 $E = 1599$ 上是 1018 对 1021， $V = 800$ 、 $E = 3199$ 上反过来是 1349 对 1338。差值两个方向都出现过。原因是 dist 出现并列时两种堆的出堆次序不同，后续哪些松弛还能成功随之改变。只有在没有并列距离的图上这个等式才严格成立。

5 · 参考文献

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.
Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), §2.4 Priority Queues. Addison-Wesley.