基于路径压缩的并查集
- 把 rank 小的树合并到 rank 大的树中，这已经是合并时的优化行为了，但是，随着合并次数的增多，树的 rank 会越来越大，其实树的形状是有进一步优化的空间的，让树的高度尽可能的矮，最理想的情况，所有的树高度为 2；
- 具体做法是：find 的时候，p 既代表待查询的元素在集合中的位置，也是找待查询元素的根节点的一个游标，p 作为游标一直向树根移动，每次找 p 的根节点的时候，只要游标 p 还没指向根节点，就让游标 p 指向的元素上移一层，然后游标 p 追到上移后的位置的父元素上，直到游标 p 追到根节点，此时，找到原 p 元素的根的同时，整棵树的层数也减少了，随着 find 操作的增多，这棵树最终是有可能变成高度只有 2 的树，从而完成路劲压缩；
- 路劲压缩后，rank 就无法准确的表示树的高度了，不过没关系，其只作为合并时的参考；
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
性能测试
package _11._06;
import java.util.Random;
public class Main {
private static double testUF(UF uf, int m){
int size = uf.getSize();
Random random = new Random();
long startTime = System.nanoTime();
for(int i = 0 ; i < m ; i ++){
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.unionElements(a, b);
}
for(int i = 0 ; i < m ; i ++){
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.isConnected(a, b);
}
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
return time;
}
public static void main(String[] args) {
int size = 10000000;
int m = 10000000;
UnionFind3 uf3 = new UnionFind3(size);
System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");
UnionFind4 uf4 = new UnionFind4(size);
System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");
UnionFind5 uf5 = new UnionFind5(size);
System.out.println("UnionFind5 : " + testUF(uf5, m) + " s");
}
}
输出：
- 有一定提升；
UnionFind3 : 5.7276717 s
UnionFind4 : 5.5825732 s
UnionFind5 : 4.5744065 s
