基于 Rank 優(yōu)化的并查集
- Rank 就是每棵子樹的高度；
- 在基于 size 的優(yōu)化的并查集中有一個(gè)問題：size 小的子樹的高度并一定就一定小于 size 大的樹，size 大的子樹的高度可能就是 2，size 小的子樹的高度也可能大于 2；
- 合并時(shí)優(yōu)化的目的是合并后的樹的高度最小壹店，樹的高度越小，查找時(shí)的路勁就越短芝加，速度相應(yīng)也越快硅卢；
- 因此用表示每棵子樹的高度的數(shù)組
rank代替表示每棵子樹節(jié)點(diǎn)多少的數(shù)組sz；
public class UnionFind4 implements UF {
private int[] rank; // rank[i]表示以i為根的集合所表示的樹的層數(shù)
private int[] parent; // parent[i]表示第i個(gè)元素所指向的父節(jié)點(diǎn)
// 構(gòu)造函數(shù)
public UnionFind4(int size){
rank = new int[size];
parent = new int[size];
// 初始化, 每一個(gè)parent[i]指向自己, 表示每一個(gè)元素自己自成一個(gè)集合
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
// 查找過程, 查找元素p所對應(yīng)的集合編號
// O(h)復(fù)雜度, h為樹的高度
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不斷去查詢自己的父親節(jié)點(diǎn), 直到到達(dá)根節(jié)點(diǎn)
// 根節(jié)點(diǎn)的特點(diǎn): parent[p] == p
while(p != parent[p])
p = parent[p];
return p;
}
}
基于 Rank 優(yōu)化后的合并操作
- 合并的時(shí)候藏杖，哪棵樹的 rank 小将塑，把哪棵樹合并于 rank 大的樹，合并完了不用更新 rank 大的樹的rank 值蝌麸，因?yàn)?rank 小的樹的高度最大比 rank 大的樹的 rank 小 1点寥，合并完了 rank 小的樹的“腳”不會伸出來；
- 只有兩棵樹的 rank 值相等祥楣，容納另一顆樹的 rank 值需要加 1开财；
// 合并元素p和元素q所屬的集合
// O(h)復(fù)雜度, h為樹的高度
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// 根據(jù)兩個(gè)元素所在樹的rank不同判斷合并方向
// 將rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot;
else if(rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此時(shí), 我維護(hù)rank的值
}
}
性能比較
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();
return (endTime - startTime) / 1000000000.0;
}
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");
}
}
輸出：
- 測試結(jié)果不是很明顯汉柒；
UnionFind3 : 5.7852983 s
UnionFind4 : 5.402423 s
