蓝桥杯python备赛笔记之（七）并查集 & 堆
前言
整篇笔记共分为十章，都是博主在准备25年蓝桥杯时所写，听的网课是这个，讲的非常好，很适合零基础速成，如果有听不懂的可以多听几遍
https://www.bilibili.com/video/BV1Zs9VYrEgg?spm_id_from=333.788.videopod.sections&vd_source=5edde23df276e6fb4a94821fa44f38b5
目录如下：
1.Python语法基础及算法入门
2.语法进阶&常用数据结构&算法入门
3.贪心&排序
4.哈希&暴力&前缀
5.二分查找&二分答案
6.搜索&BFS&DFS
7.[数据结构]并查集&堆
8.动态规划
9.图论
10.数论基础&日期问题
目录
论文投稿：
2026计算机科学与量子信息技术国际会议
大会官网：https://ais.cn/u/FfUFRv
大会时间：2026年3月27-29日
大会地点：中国-南京
一、并查集
核心概念
并查集（Disjoint Set Union，DSU）是一种高效的处理动态连通性问题的数据结构，主要支持 ** 查找（Find）和合并（Union）** 两个核心操作，能快速判断两个元素是否属于同一集合、将两个不相交的集合合并，时间复杂度经优化后接近O(1)，是蓝桥杯笔试 / 编程题中高频考点，常出现在图论、连通性、分组类问题中。
核心操作
1. 初始化
用数组fa（父节点数组）存储每个元素的父节点，初始时每个元素的父节点是自身，即每个元素独立为一个集合。
# 初始化并查集，n为元素总数（元素编号建议从0/1开始，蓝桥杯常从1开始）
def init(n):
global fa
fa = [i for i in range(n + 1)] # 元素1~n
2. 查找（Find）：找元素所属集合的根节点
基础版：递归查找根节点，未优化时存在链状结构导致效率低的问题。
# 基础查找：找x的根节点
def find(x):
if fa[x] == x: # 自身是根节点，直接返回
return x
return find(fa[x]) # 递归找父节点的根
路径压缩（核心优化）：查找时将路径上所有节点的父节点直接指向根节点，彻底解决链状结构的效率问题，是蓝桥杯必写优化！
# 带路径压缩的查找（递归版，简洁易写，蓝桥杯推荐）
def find(x):
if fa[x] != x:
fa[x] = find(fa[x]) # 路径压缩：让x直接指向根节点
return fa[x]
# 非递归版（避免递归深度超限，适合元素数量极大的情况）
def find(x):
while fa[x] != x:
fa[x] = fa[fa[x]] # 隔代压缩，也可直接找根后回溯更新
x = fa[x]
return x
3. 合并（Union）：将两个集合合并为一个
基础版：找到两个元素的根节点，若不同则将其中一个根节点的父节点指向另一个。
# 合并u和v所在的集合
def union(u, v):
u_root = find(u)
v_root = find(v)
if u_root != v_root: # 不同集合才合并
fa[v_root] = u_root # 将v的根节点挂到u的根节点下
按秩合并（可选优化）：在基础合并上，记录每个集合的秩（树的高度 / 大小），将秩小的集合挂到秩大的集合下，保持树的扁平化，进一步优化效率（蓝桥杯简单题路径压缩足够，难题建议搭配使用）。
# 初始化（新增rank数组）
def init(n):
global fa, rank
fa = [i for i in range(n + 1)]
rank = [1] * (n + 1) # rank[i]表示以i为根的集合的大小/高度
# 带按秩合并的union
def union(u, v):
u_root = find(u)
v_root = find(v)
if u_root == v_root:
return
# 小秩挂到大秩下，保持树扁平
if rank[u_root] < rank[v_root]:
fa[u_root] = v_root
else:
fa[v_root] = u_root
if rank[u_root] == rank[v_root]:
rank[u_root] += 1
并查集完整模板（蓝桥杯 Python 标准版）
兼顾路径压缩 + 按秩合并，适配绝大多数蓝桥杯题目，直接复制使用即可：
# 并查集模板（元素编号1~n，最常用）
class DSU:
def __init__(self, n):
self.fa = [i for i in range(n + 1)]
self.rank = [1] * (n + 1)
def find(self, x):
if self.fa[x] != x:
self.fa[x] = self.find(self.fa[x]) # 路径压缩
return self.fa[x]
def union(self, u, v):
u_root = self.find(u)
v_root = self.find(v)
if u_root == v_root:
return False # 已在同一集合，合并失败
# 按秩合并
if self.rank[u_root] < self.rank[v_root]:
self.fa[u_root] = v_root
else:
self.fa[v_root] = u_root
if self.rank[u_root] == self.rank[v_root]:
self.rank[u_root] += 1
return True # 合并成功
# 使用示例
if __name__ == "__main__":
dsu = DSU(5) # 初始化5个元素的并查集
dsu.union(1,2)
dsu.union(2,3)
print(dsu.find(3) == dsu.find(1)) # True，同一集合
print(dsu.find(3) == dsu.find(4)) # False，不同集合
蓝桥杯考法与解题思路
- 连通性判断：如判断图中两点是否连通、岛屿数量、朋友圈问题；
- 分组统计：统计最终有多少个不相交的集合；
- 搭配图论：最小生成树（Kruskal 算法）的核心依赖并查集判断边是否成环；
- 字符串 / 自定义元素映射：若元素是字符串 / 非连续数字，用字典
fa替代数组，键为元素，值为父节点。
注意事项
- 元素编号：蓝桥杯题目中元素常从 1 开始，初始化时注意数组长度为
n+1，避免索引越界； - 递归深度：Python 默认递归深度约 1000，若题目元素数量极大（如105以上），建议使用非递归版
find； - 字典版适配：当元素不是连续整数时，初始化字典，默认
fa[x] = x。
二、堆（优先队列）
核心概念
堆是一种完全二叉树结构，分为大根堆和小根堆：
- 小根堆：每个父节点的值 ≤ 子节点的值，堆顶（根节点）是整个堆的最小值；
- 大根堆：每个父节点的值 ≥ 子节点的值，堆顶是整个堆的最大值。
Python 中内置的heapq模块实现了小根堆，是蓝桥杯处理 **TopK 问题、贪心问题、最短路径（Dijkstra）** 的核心工具，无需手动实现堆结构，直接调用 API 即可。
Python heapq 模块核心操作（必记）
heapq的所有操作都基于列表实现，且列表会被自动维护为小根堆结构，堆顶始终是列表第一个元素。
1. 堆的初始化
- 空堆：直接创建空列表，通过
heappush逐步添加元素； - 已有列表建堆：用
heapq.heapify()原地建堆，时间复杂度O(n)（远快于逐个 push 的O(nlogn)）。
import heapq
# 方式1：空堆+逐个添加
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2) # 堆内：[1,3,2]，始终保持小根堆结构
# 方式2：已有列表原地建堆
nums = [3,1,2]
heapq.heapify(nums) # nums变为[1,3,2]，小根堆
2. 获取并弹出堆顶（最小值）
heapq.heappop(heap)：弹出堆顶元素，同时自动维护堆结构，时间复杂度O(logn)。
top = heapq.heappop(heap) # 弹出1，堆变为[2,3]
print(top) # 1
3. 获取堆顶（不弹出）
直接取列表第一个元素heap[0]，时间复杂度O(1)。
print(heap[0]) # 2，仅查看堆顶
4. 堆的扩展操作（蓝桥杯高频）
（1）实现大根堆
Pythonheapq无原生大根堆，将所有元素取负数，存入小根堆，此时堆顶是原数据的最大值，弹出后取负即可恢复原数。
# 大根堆实现：存储负数
nums = [3,1,2]
max_heap = [-x for x in nums]
heapq.heapify(max_heap) # [-3,-1,-2]，小根堆堆顶是-3，对应原数3
top = -heapq.heappop(max_heap) # 弹出3，原数的最大值
print(top) # 3
（2）TopK 问题（取前 K 大 / 前 K 小）
- 前 K 小：直接用小根堆，弹出 K 次即可；
- 前 K 大：用大根堆（负数小根堆），弹出 K 次；或用小根堆维护 K 个元素，效率更高（适合大数据量）。
# 示例：取前2大的数，nums = [5,1,9,3,7]
nums = [5,1,9,3,7]
k = 2
# 方法1：大根堆（适合小数据量）
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
top2 = [-heapq.heappop(max_heap) for _ in range(k)]
print(top2) # [9,7]
# 方法2：小根堆维护K个元素（适合大数据量，空间复杂度O(k)）
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap) # 弹出最小值，保持堆内只有K个最大的数
top2 = sorted(min_heap, reverse=True) # [9,7]
（3）堆中存储元组
蓝桥杯常需按优先级排序（如带权重的节点），可将(优先级, 数据)存入堆，heapq会按元组第一个元素排序。
# 示例：按距离排序，存储(距离, 节点)
heap = []
heapq.heappush(heap, (2, 'A'))
heapq.heappush(heap, (1, 'B'))
heapq.heappush(heap, (3, 'C'))
print(heapq.heappop(heap)) # (1, 'B')，按第一个元素升序
堆的经典应用（蓝桥杯必考场景）
- TopK 问题：如取数组前 K 大 / 小、第 K 大元素；
- 贪心算法：如任务调度、哈夫曼编码、合并 K 个有序链表；
- 图论最短路径：Dijkstra 算法（用堆维护未访问节点的最短距离）；
- 数据流的中位数：用大根堆存左半部分，小根堆存右半部分，快速获取中位数。
蓝桥杯实战模板（Dijkstra 算法，堆的核心应用）
import heapq
# Dijkstra：求起点start到所有节点的最短距离，邻接表graph
def dijkstra(graph, n, start):
INF = float('inf')
dist = [INF] * (n + 1) # 距离数组
dist[start] = 0
heap = []
heapq.heappush(heap, (0, start)) # (距离, 节点)
while heap:
cur_dist, u = heapq.heappop(heap)
if cur_dist > dist[u]: # 已找到更短路径，跳过
continue
for v, w in graph[u]: # graph[u] = [(v, 权重), ...]
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
# 使用示例
if __name__ == "__main__":
n = 4 # 节点1~4
graph = [[] for _ in range(n+1)]
graph[1] = [(2, 1), (3, 4)]
graph[2] = [(3, 2), (4, 5)]
graph[3] = [(4, 1)]
dist = dijkstra(graph, n, 1)
print(dist) # [inf, 0, 1, 3, 4]
注意事项
heapq是小根堆，大根堆需通过负数实现，注意弹出后取负恢复；heapify是原地操作，直接修改原列表，无返回值；- 堆的操作仅保证堆顶是最值，堆内其他元素无序，若需有序结果，需弹出后整理；
- Python 中堆的元素需可比较，存储自定义对象时需实现比较方法，或用元组包装。
三、蓝桥杯备考小贴士
- 模板熟记：并查集（类版）、堆的核心操作、Dijkstra 算法（堆实现）需背熟，考试直接复制修改；
- 细节把控：并查集的元素编号、堆的大根堆实现、索引越界问题是蓝桥杯高频丢分点；
- 时间复杂度：并查集（路径压缩 + 按秩合并）O(α(n))（α 为阿克曼函数，接近常数），堆的 push/pop O(logn)，适合大数据量；
- 刷题侧重：并查集重点刷Kruskal 最小生成树、连通性统计，堆重点刷TopK、Dijkstra、贪心类题目，蓝桥杯真题中这两类题型占比极高。
小龙虾开发者社区是 CSDN 旗下专注 OpenClaw 生态的官方阵地，聚焦技能开发、插件实践与部署教程，为开发者提供可直接落地的方案、工具与交流平台，助力高效构建与落地 AI 应用
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)