1. 并查集（Union Find）
(1) 定义
- 并查集：也叫作 不相交集合（Disjoint Set）
- 并查集：适合解决 “连接” 相关的问题：村庄道路连接等
- 并查集：是可以用 数组 实现的 树形结构（二叉堆、优先级序列也是）
存储数据
初始化
(2) 核心操作
2个核心操作
- 合并（Union）：将两个元素所在的集合 合并为一个集合
- 查找（Find）：查找元素 所在的集合
实现思路
- Quick Find
合并（Union）的时间复杂度：
查找（Find）的时间复杂度：)
- Quick Union
合并（Union）的时间复杂度：，可优化至
，
查找（Find）的时间复杂度：%20%3C%205)
1> Quick Find
Quick Find - Union
- 时间复杂度：
Quick Find - Find
find(0) = 2
find(1) = 2
find(2) = 2
find(3) = 4
- 时间复杂度：
2> Quick Union
Quick Union - Union
- 时间复杂度：
Quick Union - Find
find(0) = 2
find(1) = 2
find(2) = 2
find(3) = 2
- 时间复杂度：
2. 优化方案
(1) 优化方案
- 基于size的优化：元素少的树 嫁接到 元素多的树
- 基于rank的优化：矮的树 嫁接到 高的树
基于size优化、基于rank优化
(2) 优化方案深入
- 路径压缩（Path Compression）：在find时使路径上的所有节点 都指向根节点，从而降低树的高度
- 路径分裂（Path Spliting）：使路径上的每个节点都指向其祖父节点
- 路径减半（Path Halving）：使路径上的每隔一个节点都指向其祖父节点
路径压缩
路径分裂、路径减半
(3) 最优方案
最优方案：Quick Union 基于rank的优化 Path Halving 或 Path Spliting
