5.1 常用数据结构：优先队列与并查集

5.1 常用数据结构：优先队列与并查集

本节摘要：优先队列（以二叉堆为实现）支持"插入"与"取最小"各耗对数时间，是 Dijkstra 堆优化与 Prim 堆优化的速度引擎；并查集支持"查归属"与"合并阵营"，在路径压缩加按秩合并的双重优化下平均近似常数，是 Kruskal 与一切连通性判断的主力。本节讲两者的实现要点、复杂度账目与"什么时候不该用"的边界。

本节导读

阅读完本节，你应当能够：

1. 画出二叉堆的数组表示，说明上浮与下沉两个修复动作；
2. 写出支持懒删除的堆用法（配合距离校验）；
3. 实现双重优化的并查集并解释其复杂度来源；
4. 判断一个具体算法该用数组扫描还是堆、该用 DFS 还是并查集。

一、优先队列：反复"取最小"的场景引擎

回顾两个调用场景：Dijkstra 每轮要取"当前估计距离最小的未确定点"；Prim 每轮要取"横跨树边界最小的边"。共同模式是反复插入元素、反复取最小——这正是优先队列的接口。数组也能干（每次线性扫最小），但当"插入次数与取最小次数都是边数量级"时，数组扫描的总代价是平方级，堆把它压成"次数乘 log 次数"。

二叉堆的结构：一棵近似完全的二叉树，每个节点不大于（小根堆）其子节点；用数组存储，下标 i 的孩子是 2i 加 1 与 2i 加 2、父节点是 i 减 1 除以 2——无需指针。

两个修复动作：插入时把新元素放到末尾再上浮（与父节点交换直到不再小于父）；取最小时弹出根，把末尾元素补到根再下沉（与较小的孩子交换直到两个孩子都不更小）。两个动作都沿着树高走，代价为 log n。建堆可以自底向上批量完成，线性时间。

图算法里的懒删除：堆不支持"降低某个元素的键值"（Dijkstra 松弛时想更新某点的距离）。标准变通是塞新条目、弹出时校验：松弛成功就插入一条新的（更小距离, 顶点）记录；弹出时若记录的距离已经落后于账面距离，说明是过期条目，直接丢弃。堆里同一顶点可以有多份记录，但每条边至多贡献一次有效松弛，总复杂度不变。

import heapq
pq = []
heapq.heappush(pq, (3, 'B'))       # 插入 距离3 的顶点B
d, u = heapq.heappop(pq)           # 取距离最小的条目
if d > dist[u]:
    ...                            # 过期条目 丢弃 这就是懒删除
​

二、并查集：反复"问归属"的场景引擎

Kruskal 每审一条边要问"两端同阵营吗"；动态连通性场景（边一条条加入，随时问"两点连通吗"）同样如此。DFS 也能判连通，但每次询问都要整块重跑，边的加入是增量、询问却全量重算，代价失衡。并查集把两个操作都做到增量维护。

实现（与 3.3 节同一份代码，这里聚焦复杂度账目）：

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # 路径压缩 半程跳跃
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra  # 按秩合并
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
​

复杂度来源：单独使用路径压缩或单独按秩合并，单次操作最坏都是对数级；两者齐用后，"n 次操作的总代价"被压到"n 乘以阿克曼反函数"——该函数增长极慢，现实任何规模下不超过 4，按常数对待即可。工程上甚至可以不要 rank 只留路径压缩，实测同样飞快，代码更短。

适用边界：并查集只支持"并"与"查"，不支持拆分（边还会撤销的动态场景需要更复杂的离线技巧或 Link-Cut 树）。此外，若问题只有一次性询问（建好图后问一遍连通性），一次 DFS 就够，不必上并查集——工具按操作频率选。

三、两者对比与配套选型

一个综合的判断框架：先数操作模式——"反复取最小"上堆，"反复问归属加合并"上并查集，"一次性查询"用朴素方法（数组扫描或 DFS）。再数操作次数——次数小（比如点数在百级），朴素方法的常数优势可能反超对数结构。最后看特殊结构——斐波那契堆理论上能把 Dijkstra 推到"边数加 点数 log 点数"，但实现复杂、常数大，实际几乎从不胜出（这是 5.2 节解剖的主角之一）。

⚠️ 常见坑：给堆实配"删除任意元素"接口（用哈希定位再调整），复杂度账面好看、常数惨不忍睹——图算法场景一律懒删除。并查集的坑是"不写 find 直接比较代表元素"（代表会随合并漂移），以及递归版 find 在长链上爆栈——迭代加路径压缩是稳妥写法。

💡 关键直觉：两个结构对应两种"重复问话"：堆回答"现在谁最小"，并查集回答"你们是不是一伙的"。数据结构的本质是给高频问话做缓存——识别问话模式，结构自然浮现。

四、深入一层：结构选型的"频率账本"

把本章的选型逻辑抽象成一个可复用的工具——频率账本：列出你的算法要回答的高频问话，数清每类的次数与当前代价，然后为最贵的那类问话配专用结构。Dijkstra 的问话是"谁的距离最小"（数百万次、每次线性扫——配堆）；Kruskal 的问话是"这两端同阵营吗"（边数次、每次整块 DFS——配并查集）。反例同样说明问题：问话只有一次的场景（建好图问一遍连通性），配结构就是纯亏——结构的维护成本也是账。

这本账还有两个进阶条目。摊还视角：并查集的"近常数"是摊还意义上的，允许个别操作慢、看管总开销；缓存视角：堆对数因子之外，数组堆与指针堆在缓存命中上的差距常达数倍，工程实现默认选数组形态。三个视角合起来，你在 code review 里看到任何"扫描全部候选"的内层循环，都能立刻报价："这行代码值多少复杂度、换什么结构能省、代价是什么"。

常见疑问解答

语言自带的优先队列不够用时怎么办？

大多数自带实现不提供降键（这正是懒删除变通的由来）。真需要高效降键时有三条路：二叉堆加"条目冗余"（即懒删除，本节方案）；索引堆（堆内维护"位置索引"数组，支持定位更新）；换斐波那契堆（理论最优、常数吃亏，见 5.2 节解剖）。默认懒删除，量到瓶颈再升级。

并查集的 rank 数组可以省吗？

可以。只做路径压缩不做按秩合并，最坏复杂度退化为对数级（而非近常数），但实测与双优化差距很小，代码却更短。反过来只做按秩不做压缩，性能明显更差。结论：懒就只留压缩，讲究就两个都上，唯独别只用按秩。

堆和排序什么时候互换？

"一次性全量取用"用排序（Kruskal 排一次扫到底），"边产生边取用"用堆（Dijkstra 的松弛随时插入新条目）。把 Kruskal 改成堆版属于负优化，把 Dijkstra 改成"每次全排序"更是灾难——结构与操作的时间分布必须匹配。

数据结构选错了，症状通常是什么？

两类典型症状：复杂度层面——数据翻倍、耗时翻四倍以上（平方级抬头），或吞吐随操作次数急剧劣化；体验层面——小样例全对、大数据超时。定位方法是给"问话次数"打点统计，最贵的那类问话自然浮出水面，然后对号入座换结构。

动手实验：三向对决——数组、堆、并查集错配的代价

一个刻意设计的对比实验能把这些结构的选择逻辑焊进记忆。任务：在同一个万点图上实现三种"Kruskal 判环"——每次审边时全图 DFS 判连通（结构错配）、每次线性扫"已选边列表"查环（结构缺失）、标准并查集。三者正确性相同，耗时依次差一到两个数量级。再做一个镜像实验：对同一批数据只问一次连通性，并查集与一次 DFS 打平——结构按频率付费的账本在秒表上写得清清楚楚。两个实验合计一小时，换来的是"见到扫描就想换结构"的条件反射。

选型的最后一张便签

把本节收束成三行便签贴在代码仓库里：反复取最小上堆，反复问归属上并查集，只问一次就用朴素法；操作次数小（千级以内）时朴素法的常数常胜对数结构；任何"删除任意元素"的需求先试懒删除，真需要索引堆时通常说明模型该换了。三行字覆盖了图算法工程里九成的结构决策。

两个结构可以在同一个算法里同时用吗？

可以，且是成熟搭配：某些"带限制的 Kruskal"（按边权排序的同时维护优先队列做延迟删除）、求解斯坦纳树等混合问题的算法，都会让堆负责"挑当前最优"、并查集负责"判合法性"，各司其职。判断能否混用的标准很简单——看两类问话是否都高频出现：都高频就都配，单边高频就单配，谁都不高频就都别配。

本节速览

• 堆的两个动作：上浮修插入、下沉修取最小，代价 log 级；数组存完全二叉树免指针。
• 懒删除：松弛即插入新条目、弹出时校验过期，避免实现真正的降键。
• 并查集双优化：路径压缩加按秩合并，总代价近线性；只留压缩的简版实战同样够用。
• 边界一：并查集不能拆分，有撤销操作的场景要另寻他法。
• 边界二：一次性连通询问用 DFS 即可，别为单次查询维护结构。
• 稠密图反转：边数接近平方级时数组扫描的朴素 Dijkstra/Prim 可能反超堆版。
• 选型框架：问操作模式、数操作次数、查特殊结构，三步定结构。

结构备齐，下一节用复杂度分析这把"手术刀"解剖性能瓶颈，并以 Dijkstra 的三档实现为标本看理论与工程的分野。