上篇介紹了并查集的基本實現(xiàn)棺蛛，這篇介紹幾種并查集的優(yōu)化方法摄闸。
1.基于size優(yōu)化：
上一篇當(dāng)中樹實現(xiàn)并查集的方法中對要合并的兩個元素所在的樹的形狀沒有做任何的判斷塔沃，合并的過程中可能不斷增加樹的高度阵翎，使查找的性能變差院领，甚至在極端情況下，極有可能使樹退化成鏈表結(jié)構(gòu)挣菲，使查詢的時間復(fù)雜度退化到O(n)富稻。
那么該如何進(jìn)行優(yōu)化呢？首先我們維護(hù)一個數(shù)組白胀，存放每棵樹的元素的個數(shù)，每次合并時先將要合并的兩個元素對應(yīng)的樹的元素進(jìn)行比較抚岗，把樹的元素少的節(jié)點(diǎn)指向樹的元素多的節(jié)點(diǎn)上或杠。
上圖，如果要將6和9合并宣蔚，在不比較樹的元素個數(shù)的情況下向抢，可能合并的結(jié)果如下圖所示：
如果比較樹的元素的個數(shù)，合并的結(jié)果如下圖所示胚委，樹的高度和上圖比小1
代碼實現(xiàn)：
public class UnionFind3 implements UF {
int[] parent;
int[] sz; //sz[i] 表示以i為根節(jié)點(diǎn)的元素色個數(shù)
public UnionFind3(int size){
parent = new int[size];
sz = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
sz[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找i對應(yīng)的集合編號
//時間復(fù)雜度為O（h）,h為樹的高度
private int find(int i){
if(i < 0 || i>= parent.length)
throw new IllegalArgumentException("非法索引");
while (i != parent[i])
i = parent[i];
return i;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//合并操作
//時間復(fù)雜度為O（h）,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 {
parent[qRoot] =pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
大致測一下性能挟鸠，和沒優(yōu)化之前比較。
測試代碼：
public class Test {
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 = 100000;
int m = 100000;
UnionFind1 unionFind1 = new UnionFind1(size);
System.out.println("UnionFind1: " + testUF(unionFind1,m) + " s");
UnionFind2 unionFind2 = new UnionFind2(size);
System.out.println("UnionFind2: " + testUF(unionFind2,m) + " s");
UnionFind3 unionFind3 = new UnionFind3(size);
System.out.println("UnionFind3: " + testUF(unionFind3,m) + " s");
/*UnionFind4 unionFind4 = new UnionFind4(size);
System.out.println("UnionFind4: " + testUF(unionFind4,m) + " s");
UnionFind5 unionFind5 = new UnionFind5(size);
System.out.println("UnionFind5: " + testUF(unionFind5,m) + " s");
UnionFind6 unionFind6 = new UnionFind6(size);
System.out.println("UnionFind6: " + testUF(unionFind6,m) + " s");*/
}
}
執(zhí)行結(jié)果
由執(zhí)行結(jié)果大致可以清楚優(yōu)化后的速度比優(yōu)化前要快很多亩冬，所以這種優(yōu)化是很有必要的艘希。
2.基于rank的優(yōu)化
上面基于size的優(yōu)化看似沒有問題，性能也較優(yōu)化前提升了不少硅急，其實還是有問題的覆享，有的時候以樹的元素個數(shù)為判斷標(biāo)準(zhǔn)會出現(xiàn)這樣的問題：深度大的節(jié)點(diǎn)指向了深度小的節(jié)點(diǎn)，從而使合并后的樹的深度更大营袜。
那么撒顿，基于上述的問題，可以用基于rank的優(yōu)化來解決荚板，在介紹壓縮路徑之前凤壁，可以先將rank理解為樹的深度吩屹，通過一個數(shù)組來維護(hù)樹的深度，每次合并前都先比較要合并的兩個元素所在的樹的深度的大小拧抖，將深度小的節(jié)點(diǎn)指向深度大的節(jié)點(diǎn)煤搜，以達(dá)到使合并后的樹的深度不至于過大的目的。
上面后一種方法比前一中方法合并后樹的深度小1徙鱼，當(dāng)數(shù)據(jù)量很大時宅楞，這樣的優(yōu)化還是能提升一些性能的。
代碼實現(xiàn)
public class UnionFind4 implements UF {
int[] parent;
int[] rank; //rank[i] 表示以i為根節(jié)點(diǎn)的集合所表示的樹的層數(shù)
public UnionFind4(int size){
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找i對應(yīng)的集合編號
//時間復(fù)雜度為O（h）,h為樹的高度
private int find(int i){
if(i < 0 || i>= parent.length)
throw new IllegalArgumentException("非法索引");
while (i != parent[i])
i = parent[i];
return i;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//合并操作
//時間復(fù)雜度為O（h）,h為樹的高度
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
//根據(jù)兩個元素所在的樹的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] 以pRoot和qRoot為根節(jié)點(diǎn)的兩棵樹層數(shù)一樣時,合并時可以將任意一個合并到另一個即可
parent[pRoot] = qRoot;
rank[qRoot] += 1; //合并完成后層數(shù)加1
}
}
}
性能測試
代碼同上袱吆，加上幾句即可（測試數(shù)據(jù)增大厌衙，比較更明顯）
int size = 10000000;
int m = 10000000;
System.out.println("UnionFind4: " + testUF(unionFind4,m) + " s");
UnionFind5 unionFind5 = new UnionFind5(size);
執(zhí)行結(jié)果：
