数据结构：并查集（概念，代码实现，并查操作优化）

数据结构：并查集（概念，代码实现，并查操作优化）"/>

数据结构：并查集（概念，代码实现，并查操作优化）

目录

• 1.表示集合关系
• 2.并查集的代码实现
• • 1.基本操作：查
  • 2.基本操作：并
• 3.并查集的优化
• • 1.并（Union）操作的优化
  • 2.Find操作的优化（压缩路径)

1.表示集合关系

用互不相交的树，表示多个集合。
①查：查找元素归属的集合。（找树的根结点）
判断两个元素是否属于同一集合。(判断根节点是否相同)
②并：将两个集合合并为一个集合。（让一棵树成为另一棵树的子树即可）

所以能使用“并”和“查”两个操作的集合，就称之为并查集。
并查集（ Disjoint Set）是逻辑结构――集合的一种具体实现，只进行“并”和“查”两种基本操作。

2.并查集的代码实现

存储结构采用顺序存储，双亲表示法，并和查两个操作会更为简单。
（双亲表示法相关内容，请看博主这篇文章：=1001.2014.3001.5502）

1.基本操作：查

Find ——“查”操作:确定一个指定元素所属集合.
最坏时间复杂度:O(n)

2.基本操作：并

Union ——“并”操作:将两个不想交的集合合并为一个.
时间复杂度:O(1)

3.并查集的优化

核心思想:尽可能让树变矮.

1.并（Union）操作的优化

目的：为了尽可能地降低合并后树的高度，从而降低时间复杂度。
①用根节点的绝对值表示树的结点总数。
②Union操作，让小树合并到大树。

该方法构造的树高不超过 [ l o g 2 n ] + 1 [log_2^n]+1 [log2n​]+1（向下取整）
Union操作优化后，Find操作最坏时间复杂度: O ( l o g 2 n ) O(log_2^n) O(log2n​)
最坏时间复杂度：将n个独立元素通过多次Union合并为一个集合―—O(nlog2n)

2.Find操作的优化（压缩路径)

压缩路径：Find操作，先找到根节点，再将查找路径上所有结点都挂到根结点下。
目的是为了方便下一次查找元素。

每次Find操作，先找根，再“压缩路径”，可使树的高度不超过O(a(n))。
a(n)是一个增长很缓慢的函数，对于常见的n值，通常α(n)<4，因此优化后并查集的Find、Union操作时间开销都很低。
最坏时间复杂度：将n个独立元素通过多次Union合并为一个集合―—O(n a(n))。