[并查集]并查集的升级路线(四)
路径压缩并查集
并查集在经过了quick-find、quick-union、加权quick-union的演化之后，我们拥有了一个暂时看起来非常不错的算法，就是加权quick-union。经过分析和总结后，加权quick-union的操作可以将树的深度控制在log(n)的级别，相较于单纯的quick-union已然是一个不错的选择，但是进一步优化，可不可以将log(n)提升呢？甚至打到O(1)的时间复杂度？
要想在进一步优化，那么就需要保证并查集中每一颗树的深度都可以在常熟级别内，那么，需要做的事情，就是在树的构建过程中，不断把路径压缩，从而达到减少find操作的深度。
举个例子
image.png
图中所示，这是一颗不平衡的树，从根节点的4到叶子节点的0一共有5层，如果我们将0的父节点不再是指向1，而是指向2，那么树的深度也就可以由5层变为4层，完成了路径压缩。如下图
image.png
那么问题来了，应该在哪一个环节进行这样的改造呢？
还是从代码层面来分析一下
package com.zt;
public class WeightedQuickUnionUnionFind extends UnionFind {
// 分量权重数组,数组里的值代表当前分量下的分量数量
private int[] weightArr ;
public WeightedQuickUnionUnionFind(int n) {
super(n);
weightArr = new int[n];
// 初始化权重数组,初始化是每个分量下的权重都为1
for (int i = 0; i < weightArr.length; i++) {
weightArr[i] = 1;
}
}
@Override
void union(int p, int q) {
// 找到p的标识
int pId = find(p);
// 找到q的标识
int qId = find(q);
// 如果两个标识相等,代表已经合并
if (pId == qId) return;
// 将权重小的树,合并到权重大的树下
if (weightArr[pId] < weightArr[qId]) {
id[pId] = qId;
weightArr[qId] += weightArr[pId];
} else {
id[qId] = pId;
weightArr[pId] += weightArr[qId];
}
// 每次合并操作,会降低一个不同分量组
count--;
}
@Override
int find(int p) {
// 沿着标识路径一路寻找,直到找到树的标识
while (p !=id[p]) p = id[p];
return p;
}
}
由代码中可以发现，其实我们在寻找p或者q的标识的时候，默认情况下就需要遍历这棵树的层级，而且，除了遍历以外的事情我们都没有做，这样单纯的遍历，一定程度上浪费了一些性能，那么不妨从这里入手，我们把find方法进行一下改造。
改造的办法也很简单，就是在加权quick-union的find方法中再做一次小的变化
package com.zt;
public class PathCompressionQuickUnionUnionFind extends UnionFind {
// 分量权重数组,数组里的值代表当前分量下的分量数量
private int[] weightArr;
public PathCompressionQuickUnionUnionFind(int n) {
super(n);
weightArr = new int[n];
// 初始化权重数组,初始化是每个分量下的权重都为1
for (int i = 0; i < weightArr.length; i++) {
weightArr[i] = 1;
}
}
@Override
void union(int p, int q) {
// 找到p的标识
int pId = find(p);
// 找到q的标识
int qId = find(q);
// 如果两个标识相等,代表已经合并
if (pId == qId) return;
// 将权重小的树,合并到权重大的树下
if (weightArr[pId] < weightArr[qId]) {
id[pId] = qId;
weightArr[qId] += weightArr[pId];
} else {
id[qId] = pId;
weightArr[pId] += weightArr[qId];
}
// 每次合并操作,会降低一个不同分量组
count--;
}
@Override
int find(int p) {
// 沿着标识路径一路寻找,直到找到树的标识
while (p != id[p]) {
// 将父节点指向父节点的父节点,完成一次压缩操作
id[p] = id[id[p]];
p = id[p];
}
return p;
}
}
样本验证
构造了一个样本数据集，来说明路径压缩的问题
-------------------------------
0 5 4
1 9 5
2 4 7
3 4 5
4 5 1
5 1 0
6 5 1
7 6 7
8 1 2
9 6 1
10 7 1
-------------------------------
未压缩路径执行结果
-------------------------------
0 1 2 3 4 5 6 7 8 9
-------------------------------
5 5 5 3 5 5 5 6 8 5
-------------------------------
image.png
压缩路径执行结果
-------------------------------
0 1 2 3 4 5 6 7 8 9
-------------------------------
5 5 5 3 5 5 5 5 8 5
-------------------------------
image.png
经过进一次的优化后，可以看到并查集中的树的层级又再一次得到了进化，深度由原来的3变为了2。
更进一步
其实通过代码可以发现，我们在路径压缩的过程中，只是简单的把父节点指向了父节点的父节点，但是实际上，我们可以直接将父节点指向根节点，就可以保证每次find操作都是在O(1)时间内
代码如下
@Override
int find(int p) {
if (p == id[p]) return p;
// 递归直接找到根节点,将分量直接指向根节点,完成彻底的路径压缩.
id[p] = find(id[p]);
return id[p];
}
实际上的代码变动也很简单，只是进行了一次递归，将分量指向根节点。
至此，我们完成了并查集的全部升级路线，实际上，即便是最终的路径压缩方案，也没办法完美的打到O(1)时间复杂度，因为我们仍然还有递归操作，但是这样也可以带来了更高的性能提升。
总结
其实从并查集的升级路线来看，我们每一次的升级改动并不大，只不过是根据实际的问题发生，找到了算法性能瓶颈点，然后一步步分析突破，最后可以得到一个优质的算法，而且，每一步的升级，都进行了样本的验证，通过样本示例可以佐证我们的方案是正确的。
展望
后续会进一步结合实际的应用，将并查集的思想和实际结合起来，能够学会更好的运用这种数据结构。
