并查集 啟發式合并詳解 + C代碼實作

并查集 啟發式合并

并查集，這是個比較簡單的東西，用森林模拟集合，集合合并則是兩顆樹的合并，查找集合則是尋找某棵樹的根節點

因為不可避免的會遇到各種合并操作，，是以可能導緻某棵樹的深度較大，，對應的則出現了并查集的路徑壓縮還有啟發式合并

這裡不将路徑壓縮，主要是這個東西比較普及了，而且了解起來不難。

是以直接進入正題：啟發式合并

啟發式合并

第一次看到這個名稱，實在劉汝佳的書上，當時還驚訝，并查集寫了一年了，還真不知道這個啟發式合并，接着看，發現實作是使用了一個rank數組，，，原書這麼說的：

一個優化是：把小的樹合并到大樹中，這樣會讓深度不太大。這個優化稱為啟發式合并。rank[i] 表示 i 的秩，并用秩來代替深度做剛才提到的啟發式合并。

然後就懵了，秩這個東西怎麼了解……

于是上網尋找，發現很多blog所描述的都和書上幾乎一模一樣。。

是以自己想辦法了解，，還好了解了

數組rank的意義

這裡舉個例子

假設我們把這些樹看成——一個個城市，而這些城市，因發展的程度被分為不同等級，比如小型城市，中型城市，大型城市，城市與城市之間可以合并，并且規定，小型城市和小型城市合并，其中一個城市會更新為中型城市，兩個中型城市合并，其中一個城市會更新為進階城市

我們再次做一個更嚴密的規則：

1. 隻有兩個同級城市合并，其中一個城市才能更新
2. 小型城市合并到大型城市中，大型城市不更新
3. 等級高的城市必須由等級低的城市組成

回到樹——這個問題

我們假設rank[a]表示樹a的等級，姑且這麼稱呼吧，叫做名稱也可以。根據上面的規則(轉換一下)，如果一棵樹的等級較高，則這棵樹的”規模“會比較高，也就是深度會深一些，根據之前的合并優化規則：

一個優化是：把小的樹合并到大樹中，這樣會讓深度不太大。

也就是把等級較低的樹合并到等級較高的樹上

總結

我們寫一個合并函數，這個函數需要根據兩棵樹的等級(rank)來判斷哪棵樹合并到另一棵樹，并且判斷一棵樹是否需要更新

代碼：

void union_ (int a,int b) {
    int x = find_(a), y = find_(b);
    if (ranks[x] > ranks[y]) {//兩棵樹一定不同級，不存在更新操作
        bcset[y] = x;
    } else {
        bcset[x] = y;
        if (ranks[x] == ranks[y]) {//兩棵同等級的樹合并，其中一棵樹更新
            ranks[y] ++;
        }
    }
}