算法 - 并查集

1. 并查集（Union Find）

(1) 定义

  • 并查集：也叫作 不相交集合（Disjoint Set）
  • 并查集：适合解决 “连接” 相关的问题：村庄道路连接等
  • 并查集：是可以用 数组 实现的 树形结构（二叉堆、优先级序列也是）
存储数据
初始化

(2) 核心操作

2个核心操作

  • 合并（Union）：将两个元素所在的集合 合并为一个集合
  • 查找（Find）：查找元素 所在的集合

实现思路

  • Quick Find
    合并（Union）的时间复杂度：O(n)
    查找（Find）的时间复杂度：O(1)
  • Quick Union
    合并（Union）的时间复杂度：O(logn)，可优化至O(α(n))，α(n) < 5
    查找（Find）的时间复杂度：O(logn)，可优化至O(α(n))，α(n) < 5
1> Quick Find
Quick Find - Union
  • 时间复杂度：O(n)
Quick Find - Find

find(0) = 2
find(1) = 2
find(2) = 2
find(3) = 4

  • 时间复杂度：O(1)
2> Quick Union
Quick Union - Union
  • 时间复杂度：O(logn)
Quick Union - Find

find(0) = 2
find(1) = 2
find(2) = 2
find(3) = 2

  • 时间复杂度：O(logn)

2. 优化方案

(1) 优化方案

  • 基于size的优化：元素少的树 嫁接到 元素多的树
  • 基于rank的优化：矮的树 嫁接到 高的树
基于size优化、基于rank优化

(2) 优化方案深入

  • 路径压缩（Path Compression）：在find时使路径上的所有节点 都指向根节点，从而降低树的高度
  • 路径分裂（Path Spliting）：使路径上的每个节点都指向其祖父节点
  • 路径减半（Path Halving）：使路径上的每隔一个节点都指向其祖父节点
路径压缩
路径分裂、路径减半

(3) 最优方案

最优方案：Quick Union 基于rank的优化 Path Halving 或 Path Spliting

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容