数据结构 —- 并查集(Union Find)
并查集有两个核心操作，查找和合并，O(1) 的时间复杂度查询两个元素是否在同一个集合，和将两个不同元素所在集合合并，时间复杂度也为O(1)。
目录
一、并查集
并查集有两种实现思路
-
Quick Find
查找(Find)的时间复杂度:0(1)
合并(Union）的时间复杂度:0(n) -
Quick Union
查找(Find）的时间复杂度: O(logn)
合并(Union)）的时间复杂度: O(logn)
Quick Union还可以继续优化，均摊复杂度到O(1)。
并查集的数据存储形式
数组的下标为数据，而对应存储的值为根节点。
- 0，1，3 为一个集合
- 2 为一个集合
-
4，5，6，7 为一个集合
存储元素为整数，可以使用数组来存储。和堆有点类似。
并查集的接口
int find(int e); //查询一个元素所在集合。返回根节点
bool isSameSet(int e1, int e2);//查询两个元素是否在同一集合
void _union(int e1, int e2);//合并两个集合
并查集的初始化
初始化时，认为每个元素都为单独的一个集合，根节点默认为自己。
Quick Find 实现
Quick Find 的合并(Union)
代码示例：
void _union(int e1, int e2) {
assert(e1 >= 0 && e1 < parent.size());
assert(e2 >= 0 && e2 < parent.size());
if (isSameSet(e1, e2)) return;//已经在同一个集合
int p1 = find(e1);//返回根节点。
int p2 = find(e2);
for (int i = 0; i < i < parent.size(); i++) {
if (parent[i] == p1) {
parent[i] = p2;
}
}
}
此时进行1 和 0 合并操作，（默认左边参数挂在右边）。
将下标为1的位置存储0的根节点。
很明显能看出Quick Find的合并操作时间复杂度为O(1)。
Quick Find 的查找(Find)
代码示例：
int find(int e) {
check(e);
return parent[e];
}
bool isSameSet(int e1, int e2) {
check(e1);
check(e2);
return find(e1) == find(e1);
}
由于合并操作，这颗树的高度始终不会超过2。实际存储数据的数组内存储的就为下标(元素)对应的根节点.
时间复杂度为O(1)。
Quick Find 完整代码
class union_find
{
public:
// 简易实现，样本量为 [0,capacity - 1]
union_find(int capacity) {
assert(capacity > 0);
for (int i = 0; i < capacity; i++) {
parent.push_back(i);
}
}
int find(int e) {
assert(e >= 0 && e < parent.size());
return parent[e];
}
bool isSameSet(int e1, int e2) {
assert(e1 >= 0 && e1 < parent.size());
assert(e2 >= 0 && e2 < parent.size());
return find(e1) == find(e2);
}
void _union(int e1, int e2) {
assert(e1 >= 0 && e1 < parent.size());
assert(e2 >= 0 && e2 < parent.size());
if (isSameSet(e1, e2)) return;//已经在同一个集合
int p1 = find(e1);
int p2 = find(e2);
for (int i = 0; i < i < parent.size(); i++) {
if (parent[i] == p1) {
parent[i] = p2;
}
}
}
private:
std::vector<int> parent;
};
小结
由于Quick Find实现方式的 Union操作 导致这颗逻辑上的树的高度不超过2，查找直接通过下标直接定位根节点，时间复杂度可以达到O(1)。但合并的复杂度却需要遍历整个数组，时间复杂度达到了O(N)。这种实现并不实用。
Quick Union 的实现
Quick Union 的查找(Find)
两个元素的向上找，最顶部的根节点相同，就认为在同一个集合内
int find(int e) {
assert(e >= 0 && e < parent.size());
while (e != parent[e])
e = parent[e];
return e;
}
bool isSameSet(int e1, int e2) {
assert(e1 >= 0 && e1 < parent.size());
assert(e2 >= 0 && e2 < parent.size());
return find(e1) == find(e1);
}
Quick Union 的合并(Union)
将一个集合的根节点连接在另一个集合的根节点下，就完成了合并。
void _union(int e1, int e2) {
assert(e1 >= 0 && e1 < parent.size());
if (isSameSet(e1, e2)) return;//已经在同一个集合
int p1 = find(e1);
int p2 = find(e2);
parent[p1] = p2;
}
小结：
Quick Union 的查找和合并都要从底部向上查找，距离为树的高度，时间复杂度均为O(logN)，但是在最坏情况下，并查集退化成链表，性能就非常低下
并查集的优化
有2种常见的优化方式
基于size的优化：
- 节点少的树连接到节点多的树上
基于高度的优化:
- 矮的树嫁接到高的树
基于size
原先都是默认左树接在右树上，这会导致某些情况出现链表情况，现在通过树的大小让小的树接在大的树下。
代码示例：
需要添加一个字段保存每个节点对应的大小。
union_find(int capacity) {
assert(capacity > 0);
for (int i = 0; i < capacity; i++) {
_parent.push_back(i);
_size.push_back(1); //默认每个节点size为1
}
}
void _union(int e1, int e2) {
assert(e1 >= 0 && e1 < _parent.size());
if (isSameSet(e1, e2)) return;//已经在同一个集合
int p1 = find(e1);
int p2 = find(e2);
//默认p1 size小
if (_size[p1] > _size[p2])
std::swap(p1, p2);
_parent[p1] = p2;
_size[p2] += _size[p1];
}
基于hight
基于size的优化，出现以下情况也会导致性能下降。
代码示例：
也需要一个字段保存高度信息，初始化高度为1
void _union(int e1, int e2) {
assert(e1 >= 0 && e1 < _parent.size());
if (isSameSet(e1, e2)) return;//已经在同一个集合
int p1 = find(e1);
int p2 = find(e2);
if (_hight[p1] < _hight[p2]) {
_parent[p1] = p2;
}
else if (_hight[p1] > _hight[p2]) {
_parent[p2] = p1;
}
else {
_parent[p1] = p2;
_hight[p2]++;
}
}
路径压缩 (Path Compression)
基于rank的优化，树会相对平衡很多，但是随着Union次数的增多，树的高度依然会越来越高。
导致find操作变慢，尤其是底层节点
什么是路径压缩?
在find的时候，使路径上的所有节点都指向根节点，从而降低树的高度。
代码示例：
int find(int e) {
assert(e >= 0 && e < _parent.size());
//递归调用，一路向上所有节点都指向根节点
while (e != _parent[e])
_parent[e] = find(_parent[e]);
return _parent[e];
}
路径分裂 （Path Spliting）
路径压缩将每个节点都平铺开，这样优化的性能反而可能下降。
路径分裂: 使路径上的每个节点都指向其祖父节点(parent的parent)
int find(int e) {
assert(e >= 0 && e < _parent.size());
while (e != _parent[e]) {
int p = _parent[e];
_parent[e] = _parent[_parent[e]];
e = p;
}
return _parent[e];
}