基于每棵樹 size 的優(yōu)化
- 在并查集中增加了一個數(shù)組 sz砰逻，用于表示并查集中以每個元素為根的樹的大小彭羹，依次作為合并時誰合并于誰的依據(jù)瀑罗；
- 節(jié)點(diǎn)少的樹往節(jié)點(diǎn)大的樹合并阱缓，更不容易增加合并后樹的深度；
- 兩棵樹在合并的時候筝野，如果不加考慮，那么最后合并成的樹有可能退化成一個鏈表扭勉；
public class UnionFind3 implements UF{
private int[] parent; // parent[i]表示第一個元素所指向的父節(jié)點(diǎn)
private int[] sz; // sz[i]表示以i為根的集合中元素個數(shù)
// 構(gòu)造函數(shù)
public UnionFind3(int size){
parent = new int[size];
sz = new int[size];
// 初始化, 每一個parent[i]指向自己, 表示每一個元素自己自成一個集合
for(int i = 0 ; i < size ; i ++){
parent[i] = i;
sz[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;
}
// 查看元素p和元素q是否所屬一個集合
// O(h)復(fù)雜度, h為樹的高度
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
}
基于兩棵樹 size 優(yōu)化后的合并方法
- 兩棵樹誰的節(jié)點(diǎn)少皂冰，就合并于節(jié)點(diǎn)多的樹店展；
- 合并完了更新一下節(jié)點(diǎn)更多的那棵樹的節(jié)點(diǎn)的數(shù)量；
// 合并元素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ù)兩個元素所在樹的元素個數(shù)不同判斷合并方向
// 將元素個數(shù)少的集合合并到元素個數(shù)多的集合上
if(sz[pRoot] < sz[qRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{ // sz[qRoot] <= sz[pRoot]
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
性能比較
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) {
// UnionFind2 慢于 UnionFind1, 但UnionFind3最快
int size = 100000;
int m = 100000;
UnionFind1 uf1 = new UnionFind1(size);
System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
UnionFind2 uf2 = new UnionFind2(size);
System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");
UnionFind3 uf3 = new UnionFind3(size);
System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");
}
}
輸出：
- 基于兩棵樹的size的優(yōu)化后的速度有明顯的優(yōu)勢秃流；
- 至于為什么用數(shù)組一維表示的并查集的速度比把數(shù)組構(gòu)建成樹的并查集的速度快赂蕴，那是因?yàn)镴VM對一段連續(xù)內(nèi)存空間的遍歷操作做了非常好的優(yōu)化，而用數(shù)組表示的樹結(jié)構(gòu)舶胀，其操作是在數(shù)組間跳來跳去概说，所以速度更慢；
UnionFind1 : 5.9921952 s
UnionFind2 : 13.0992546 s
UnionFind3 : 0.018073399 s
