并查集（Union Find）

需求分析

假設(shè)現(xiàn)在有這樣一個(gè)需求，如下圖的每一個(gè)點(diǎn)代表一個(gè)村莊，每一條線就代表一條路，所以有些村莊之間有連接的路，有些村莊沒(méi)有連接的路，但是有間接連接的路

根據(jù)上面的條件，能設(shè)計(jì)出一個(gè)數(shù)據(jù)結(jié)構(gòu)，能快速執(zhí)行下面2個(gè)操作

1. 查詢兩個(gè)村莊之間是否有連接的路
2. 連接兩個(gè)村莊

為了完成上面的需求，能不能使用前面介紹的數(shù)據(jù)結(jié)構(gòu)呢，例如：數(shù)組，鏈表，平衡二叉樹，集合？其實(shí)是可以的，只是效率上高與低的問(wèn)題。

例如使用動(dòng)態(tài)數(shù)組完成上面這種操作，可以通過(guò)下面的方式完成。

1. 將每個(gè)圖用一個(gè)數(shù)組來(lái)對(duì)應(yīng)，所以在這里，需要三個(gè)數(shù)組
   • 判斷兩個(gè)村莊之間是否有連接的路
     判斷兩個(gè)元素是否在同一個(gè)數(shù)組中即可，如果兩個(gè)元素在同一個(gè)元素中，就代表它們之間，有連接的路，否則就沒(méi)有
   • 連接兩個(gè)村莊
     將兩個(gè)村莊的元素，整合到一個(gè)數(shù)組即可

其他幾種數(shù)據(jù)結(jié)構(gòu)操作也類似。但是使用這些數(shù)據(jù)結(jié)構(gòu)存在一個(gè)問(wèn)題，它們的查詢，連接時(shí)間復(fù)雜度都是O(n)，所以用這些數(shù)據(jù)結(jié)構(gòu)來(lái)完成上面的需求，不合適。但是在本節(jié)內(nèi)容中介紹的并查集能夠辦到查詢，連接的均攤時(shí)間復(fù)雜度都是O(α(n)),α(n) < 5，所以并查集非常適合解決這類“連接”相關(guān)的問(wèn)題

并查集

并查集和叫做不相交集合（Disjoint Set）

并查集有2個(gè)核心操作

1. 查找（Find）：查找元素所在的集合（這里的集合并不是特指Set這種數(shù)據(jù)結(jié)構(gòu)，是指廣義上的數(shù)據(jù)集合）
2. 合并（Union）：將兩個(gè)元素所在的集合合并為一個(gè)集合

并查集有2種常見的實(shí)現(xiàn)思路

1. Quick Find
   • 查找（Find）的時(shí)間復(fù)雜度為：O(1)
   • 合并（Union）的時(shí)間復(fù)雜度為：O(n)
2. Quick Union
   • 查找（Find）的時(shí)間復(fù)雜度為：O(logn)，可以優(yōu)化至O(α(n))，α(n) ＜ 5
   • 合并（Union）的時(shí)間復(fù)雜度為：O(logn)，可以優(yōu)化至O(α(n))，α(n) ＜ 5

所以，通過(guò)Quick Find來(lái)實(shí)現(xiàn)并查集的話，查找的效率會(huì)比Quick Union高，但是合并效率會(huì)比Quick Union低，那在開發(fā)中用哪一個(gè)呢？在開發(fā)中，一般使用Quick Union這種思路

并查集如何存儲(chǔ)數(shù)據(jù)

現(xiàn)假設(shè)并查集處理的數(shù)據(jù)都是整型，那么可以用整型數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，其中數(shù)組的索引代表對(duì)應(yīng)的元素編號(hào)，然后數(shù)組中存儲(chǔ)的數(shù)據(jù)為該元素對(duì)應(yīng)所在的集合，所以如果用下圖來(lái)表示對(duì)應(yīng)村莊對(duì)應(yīng)的集合，其中索引代表村莊的標(biāo)號(hào)，編號(hào)對(duì)應(yīng)的值代表村莊所在的集合

可以知道，村莊0,1,3是相互有路相連，村莊2/5分別獨(dú)立，沒(méi)有路與其他相連，村莊5,6,7是相互有路相連的。那么如果使用形象的圖來(lái)表示的話，村莊0,1,3，可以用下圖來(lái)進(jìn)行表示

解釋：

1. 村莊索引0的父節(jié)點(diǎn)為村莊索引1
2. 村莊索引3的父節(jié)點(diǎn)為村莊索引1
3. 村莊索引1·的父節(jié)點(diǎn)為村莊索引1

也可以認(rèn)為，索引對(duì)應(yīng)的元素，代表父節(jié)點(diǎn)的索引，所以每一個(gè)節(jié)點(diǎn)，都有一根線，指向其父節(jié)點(diǎn)，所以從這個(gè)圖，可以看出，0,1,3的父節(jié)點(diǎn)都1，所以屬于同一個(gè)集合。以此類推2表示單獨(dú)的一個(gè)集合

根據(jù)上面的定義，索引4的村莊的父節(jié)點(diǎn)索引為5，所以其實(shí)索引4與5之間是有聯(lián)系的，并且5,6,7,之間本來(lái)也存在聯(lián)系，所以最終可以用下圖來(lái)進(jìn)行表示，所以可以認(rèn)為4,5,6,7也是屬于同一個(gè)集合的。

所以，如果并查集是整數(shù)的話，就可以通過(guò)數(shù)組來(lái)表示每個(gè)元素之間的關(guān)系。所以并查集是可以用數(shù)組來(lái)實(shí)現(xiàn)的樹形結(jié)構(gòu)（二叉堆，優(yōu)先級(jí)隊(duì)列也是可以用數(shù)組實(shí)現(xiàn)的樹形結(jié)構(gòu)）

接口定義

所以，根據(jù)前面的介紹，并查集需要定義以下接口

/**
 * 查找v所屬的集合（根節(jié)點(diǎn)）
 */
int find(int v);
/**
 * 合并v1,v2所屬的集合
 */
void union(int v1, int v2);
/**
 * 檢查v1,v2是否屬于同一個(gè)集合
 */
boolean isSame(int v1, int v2);

初始化

前面介紹了并查集的兩種實(shí)現(xiàn)方式，不過(guò)，不管是使用哪種方式實(shí)現(xiàn)，都需要對(duì)數(shù)據(jù)進(jìn)行初始化，初始化時(shí)，每個(gè)元素各自屬于一個(gè)單元素集合。例如開始的時(shí)候，有如下的5個(gè)節(jié)點(diǎn)，其中索引0的元素存儲(chǔ)元素0，索引1的元素存儲(chǔ)元素1，索引2的元素存儲(chǔ)元素2，索引3的元素存儲(chǔ)元素3，索引4的元素存儲(chǔ)元素4

然后用圖來(lái)表示如下，其中，每一個(gè)元素屬于一個(gè)單元素集合，即自己成為一個(gè)集合，這樣代表所有的元素都不在同一個(gè)集合內(nèi)。

所以初始化的實(shí)現(xiàn)代碼為

public UnionFind(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity must be >= 1");
    }

    parents = new int[capacity];
    for (int i = 0; i < parents.length; i++) {
        parents[i] = i;
    }
}

Quick Find - Union

在使用Quick Find實(shí)現(xiàn)上圖的元素時(shí)，首先要進(jìn)行的是初始化，前面已經(jīng)介紹過(guò)了，所以在這里就不再贅述。初始化完成后，如果現(xiàn)在需要對(duì)1,0執(zhí)行Union操作的話，有兩種做法，即將0的箭頭，指向1，或者將1的箭頭指向0，這樣就代表兩個(gè)元素屬于同一個(gè)集合中?，F(xiàn)規(guī)定，如果執(zhí)行union(v1,v2)的話，統(tǒng)一將v1的箭頭指向v2。所以，如果現(xiàn)在執(zhí)行union(1,0)操作的話，只需要將索引為1指向的元素，值改為0即可。即下圖所示

對(duì)應(yīng)的關(guān)系圖如下

同樣的，如果要執(zhí)行union(1,2)操作的話，按照上面的操作，就是將索引為1指向的元素，改為2即可

但是修改后有一個(gè)問(wèn)題，在以前，0,1是屬于同一個(gè)集合的，現(xiàn)在1，2要變?yōu)橥粋€(gè)集合，所以還需要將索引0指向的元素也修改為2

最終的關(guān)系圖如下

執(zhí)行union(4,0)操作的話，根據(jù)上面的流程，最終得到的結(jié)果為

對(duì)應(yīng)的關(guān)系圖如下

執(zhí)行union(3,2)，得到的結(jié)果為

執(zhí)行完成后得到的關(guān)系圖如下

所以，發(fā)現(xiàn)細(xì)節(jié)了嗎？使用Quick Find來(lái)實(shí)現(xiàn)Union的話，得到的結(jié)果很平，每一個(gè)節(jié)點(diǎn)，向上找一次，就能找到自己的根節(jié)點(diǎn)。那基于這種條件，繼續(xù)在研究如何實(shí)現(xiàn)Find操作

所以合并的實(shí)現(xiàn)代碼為

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    for (int i = 0; i < parents.length; i++) {
        if (parents[i] == p1) {
            parents[i] = p2;
        }
    }
}

Quick Find - Find

如果使用的是上面這種Union方式，可以發(fā)現(xiàn)，數(shù)組中存儲(chǔ)的數(shù)據(jù)，就是每個(gè)索引元素對(duì)應(yīng)的根節(jié)點(diǎn)，所以如果有下圖的元素

對(duì)應(yīng)的關(guān)系圖為

所以根據(jù)每個(gè)索引元素對(duì)應(yīng)的根節(jié)點(diǎn)的結(jié)論可以知道，如果執(zhí)行下面的操作

• find(0)得到的結(jié)果為2
• find(1)得到的結(jié)果為2
• find(3)得到的結(jié)果為3

所以Quick Find的Find操作，時(shí)間復(fù)雜度為O(1)

查找的實(shí)現(xiàn)為

public int find(int v) {
    rangeCheck(v);
    return parents[v];
}

所以，到這里，通過(guò)Quick Find的方式，就實(shí)現(xiàn)了并查集，不過(guò)，從合并的實(shí)現(xiàn)可以發(fā)現(xiàn)，在合并時(shí)，需要對(duì)所有元素進(jìn)行一次遍歷，所以合并的時(shí)間復(fù)雜度為O(n)。接下來(lái)，再來(lái)研究并查集的另外一種實(shí)現(xiàn)Quick Union

Quick Union- Union

前面說(shuō)到，Quick Union的Find與Union時(shí)間復(fù)雜度都是O(logn)，對(duì)比Quick Find中的Union時(shí)間復(fù)雜度O(n)來(lái)講，性能提升很多，接下來(lái)就看以下，Quick Union是如何實(shí)現(xiàn)的。

首先最開始的步驟與Quick Find是一樣的，都需要初始化，每一個(gè)元素屬于一個(gè)單元素集合。即下列的5個(gè)元素

組成單元素集合后

初始化完成后，就開始利用Quick Union的思路執(zhí)行Union操作。

執(zhí)行union(1,0)，現(xiàn)依然規(guī)定，左邊的元素，跟隨右邊的元素，即這里合并后的話，是讓左邊元素的根節(jié)點(diǎn)，等于右邊元素的根節(jié)點(diǎn)。即現(xiàn)在合并的1,0，其中1的根節(jié)點(diǎn)為1,0的根節(jié)點(diǎn)為0，由于左邊元素的根節(jié)點(diǎn)等于右邊元素的根節(jié)點(diǎn)，所以合并完成后，索引1的元素，根節(jié)點(diǎn)變?yōu)?，這一步，看起來(lái)和Quick Find沒(méi)什么區(qū)別。

合并后的關(guān)系圖如下

接下來(lái)，如果繼續(xù)做union(1,2)操作的話，就有區(qū)別了。根據(jù)前面的結(jié)論，所以需要將索引1的根節(jié)點(diǎn)改為索引2的根節(jié)點(diǎn)。由于現(xiàn)在1的根節(jié)點(diǎn)為0，2的根節(jié)點(diǎn)為2，所以只需要讓兩個(gè)根節(jié)點(diǎn)來(lái)處理就好了，即讓0與2進(jìn)行連接就好了，最終就是索引為0的節(jié)點(diǎn)，父節(jié)點(diǎn)變?yōu)?。

合并后的關(guān)系圖如下

繼續(xù)執(zhí)行union(4,1)操作，所以就是將4的根節(jié)點(diǎn)指向1的根節(jié)點(diǎn)，最終需要處理的節(jié)點(diǎn)就是4,2，達(dá)到的效果就是4指向2

合并后的關(guān)系圖如下

再執(zhí)行union(0,3)，也就是說(shuō)需要將0,3進(jìn)行合并，仍然是找到0的根節(jié)點(diǎn)與3的根節(jié)點(diǎn)，然后將0根節(jié)點(diǎn)的父節(jié)點(diǎn)指向3的父節(jié)點(diǎn)即可

合并后的關(guān)系圖如下

所以，最終看到的效果就是上圖這樣，這種操作對(duì)比之前Quick Find做的union操作就不一樣了，Quick Find樹的高度，最多就是2，但是采用Quick Union這種思路的話， 永遠(yuǎn)都是找到根節(jié)點(diǎn)進(jìn)行操作，情況就不一樣了，Quick Find是將左邊集合中所有元素根節(jié)點(diǎn)，都改為右邊元素的根節(jié)點(diǎn)，Quick只需要對(duì)左邊元素的根節(jié)點(diǎn)進(jìn)行操作即可

所以實(shí)現(xiàn)代碼如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    parents[p1] = p2;
}

接下來(lái)在研究Find操作是如何實(shí)現(xiàn)的

Quick Union - Find

首先，F(xiàn)ind操作的目的是要返回當(dāng)前集合的根節(jié)點(diǎn)，所以例如下圖中的集合

對(duì)應(yīng)的關(guān)系圖如下

如果要查找1的根節(jié)點(diǎn)，就是從節(jié)點(diǎn)1開始，一直往上找，直到找到的節(jié)點(diǎn)，發(fā)現(xiàn)根節(jié)點(diǎn)是自己時(shí)，就說(shuō)明已經(jīng)找到根節(jié)點(diǎn)了，將該根節(jié)點(diǎn)進(jìn)行返回即可。

所以

• find(0)得到的結(jié)果為2
• find(1)得到的結(jié)果為2
• find(3)得到的結(jié)果為3

Find操作的時(shí)間復(fù)雜度我O(logn)，由于Find的時(shí)間復(fù)雜度為O(logn)，所以Union操作的時(shí)間復(fù)雜度也為O(logn)

Find的實(shí)現(xiàn)代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        v = parents[v];
    }
    return v;
}

這樣，Quick Union也實(shí)現(xiàn)了union與find操作。由于Quick Union與Quick Find之間時(shí)間復(fù)雜度的區(qū)別，所以建議使用性能更高的Quick Union。

Quick Union優(yōu)化

在Union的過(guò)程中，可能會(huì)出現(xiàn)樹不平衡的情況，甚至可能會(huì)退化成為鏈表，例如下圖

如果現(xiàn)在要執(zhí)行union(1,3)，按照以前的操作，是將1的根節(jié)點(diǎn)，指向3的根節(jié)點(diǎn)，所以最終的結(jié)果如下

所以，如果一直按照這種方式進(jìn)行合并的話，最終就真的會(huì)退化成為鏈表，一旦退化成為鏈表，最終find操作的時(shí)間復(fù)雜度就變?yōu)镺(n)，所以需要對(duì)前面的方案進(jìn)行優(yōu)化。

優(yōu)化方案

1. 基于size的優(yōu)化：將元素少的樹，嫁接到元素多的樹
2. 基于rank的優(yōu)化：矮的樹，嫁接到高的樹

基于size的優(yōu)化

例如有下圖的兩個(gè)集合，現(xiàn)在要將其合并

由于，現(xiàn)在是將元素少的樹，嫁接到元素多的樹上， 所以最終合并后的結(jié)果為

基于這種方式的實(shí)現(xiàn)，需要知道每個(gè)集合中有多少個(gè)元素，所以，要存儲(chǔ)以下每個(gè)集合的size，由于在初始化時(shí)，全是單元素集合，所以在初始化時(shí)，也需要將size進(jìn)行初始化，所以初始化的代碼如下

public UnionFind_QuickUnion_Size(int capacity) {
    super(capacity);
    sizes = new int[capacity];
    for (int i = 0; i < sizes.length; i++) {
        sizes[i] = 1;
    }
}

最終優(yōu)化的部分，一定是合并集合的部分，所以只需要對(duì)union函數(shù)部分的代碼進(jìn)行優(yōu)化就可以了

所以對(duì)size優(yōu)化后的代碼為

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //size少的，嫁接到size多的上
    if (sizes[p1] > sizes[p2]) {
        parents[p2] = p1;//將p2嫁接到p1上
        sizes[p1] += sizes[p2];//更新size
    } else {
        parents[p1] = p2;
        sizes[p2] += sizes[p1];
    }
}

然后現(xiàn)在對(duì)前面的幾種實(shí)現(xiàn)，利用相同數(shù)量的元素進(jìn)行對(duì)比，最終得到的結(jié)果如下

可以看到，基于size的優(yōu)化，速度非?？?，效果非常明顯。

但是，基于size的優(yōu)化，也可能存在樹不平衡的問(wèn)題。

例如需要將下圖中的兩個(gè)集合進(jìn)行合并

如果是使用基于size的優(yōu)化，最終合并的結(jié)果為

所以為了解決這種問(wèn)題，將使用基于rank的優(yōu)化

基于rank的優(yōu)化

基于rank的優(yōu)化，是不比較集合中的數(shù)量，而是比較集合中樹的高度、基于樹高進(jìn)行優(yōu)化的話，現(xiàn)在對(duì)下圖中的兩個(gè)集合進(jìn)行合并，則是將樹矮的樹，合并到樹高的樹上

所以，最終是將根節(jié)點(diǎn)為4的樹，嫁接上根節(jié)點(diǎn)為3的樹上，最終合并完成后如下

很明顯，這種優(yōu)化，從樹的平衡來(lái)講，樹會(huì)更加平衡，是由于基于size的優(yōu)化的。

基于rank的優(yōu)化，同樣需要在初始化時(shí)，初始化每個(gè)單元素集合的高度進(jìn)行初始化，所以初始化時(shí)的實(shí)現(xiàn)如下

private int[] ranks;
public UnionFind_QuickUnion_Rank(int capacity) {
    super(capacity);
    ranks = new int[capacity];
    for (int i = 0; i < ranks.length; i++) {
        ranks[i] = 1;
    }
}

與基于size的優(yōu)化相同，優(yōu)化的部分也是在合并時(shí)，所以只需要對(duì)合并部分的代碼進(jìn)行優(yōu)化即可。所以優(yōu)化后的代碼如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //rank值小的，嫁接到rank值大的樹上
    if (ranks[p1] > ranks[p2]) {
        parents[p2] = p1; //將矮的樹，嫁接到高的樹上
        //由于是矮的樹嫁接到高的樹上，所以不需要更新樹高
    } else if (ranks[p1] < ranks[p2]){
        parents[p1] = p2;
    } else {
        //樹高相等，進(jìn)行合并，所以樹高會(huì)增加1
        parents[p1] = p2;
        ranks[p2] += 1;
    }
}

最終，將優(yōu)化后的兩種方案，用更大的測(cè)試數(shù)據(jù)進(jìn)行測(cè)試后，得到的比較結(jié)果如下

可以發(fā)現(xiàn)，基于rank的優(yōu)化，表現(xiàn)同樣非常的優(yōu)秀。不過(guò)需要注意，這并不意味著基于rank的優(yōu)化性能低于基于size的優(yōu)化，因?yàn)檫@兩種優(yōu)化，出發(fā)點(diǎn)不一樣?；趓ank的優(yōu)化，主要是為了解決基于size優(yōu)化中，出現(xiàn)不平衡的情況，建議使用基于rank的優(yōu)化。

雖然兩種優(yōu)化，效果都非常好，不過(guò)仍然還有進(jìn)一步的優(yōu)化空間。接下來(lái)繼續(xù)研究關(guān)于優(yōu)化的問(wèn)題

路徑壓縮（Path Compression）

什么叫路徑壓縮呢？比如說(shuō)現(xiàn)在有如下的兩個(gè)集合

現(xiàn)在基于Quick Union并且基于rank的優(yōu)化，進(jìn)行union(1,5)合并的話，得到的結(jié)果如下

合并后，可以發(fā)現(xiàn)，雖然有了基于rank的優(yōu)化，樹會(huì)相對(duì)平衡一點(diǎn)，但是，隨著union的次數(shù)增加，樹的高度依然會(huì)越來(lái)越高，最終導(dǎo)致find操作會(huì)變得越來(lái)越慢。所以，基于這樣的問(wèn)題的存在，可以進(jìn)行路徑壓縮優(yōu)化。

路徑壓縮

• 在find時(shí)使路徑上的所有節(jié)點(diǎn)都指向根節(jié)點(diǎn)，從而降低樹的高度

這句話的意思就是說(shuō)，執(zhí)行完find操作以后，這條路徑上的所有節(jié)點(diǎn)，都直接指向根節(jié)點(diǎn)，所以例如執(zhí)行find(1)操作，執(zhí)行完成后的結(jié)果如下圖

可以發(fā)現(xiàn)，執(zhí)行完find操作后，原來(lái)路徑上的節(jié)點(diǎn)2,3,4都直接指向了根節(jié)點(diǎn)，通過(guò)這樣的優(yōu)化，樹的高度僅進(jìn)一步降低，所以如果繼續(xù)執(zhí)行find(0),find(7)操作，最終在find后，路徑上的所有節(jié)點(diǎn)，都直接指向根節(jié)點(diǎn)，所以最終的結(jié)果如下

通過(guò)這樣的優(yōu)化后，以后在進(jìn)行find操作時(shí)，就會(huì)變得非?？臁６矣捎趗nion也要使用到find，所以最終union效率也會(huì)提升。所以，最終要達(dá)到的效果就是樹越矮越好。接下來(lái)就研究，如何實(shí)現(xiàn)。

前面說(shuō)到，路徑壓縮是對(duì)find進(jìn)行優(yōu)化，所以這次需要對(duì)find方法重新實(shí)現(xiàn)，最終find的實(shí)現(xiàn)如下

public int find(int v) {
    rangeCheck(v);
    if (v != parents[v]) {
        //修改v的父節(jié)點(diǎn)，通過(guò)遞歸調(diào)用，最終找到根節(jié)點(diǎn)，將v的父節(jié)點(diǎn)指向根節(jié)點(diǎn)
        //順便將整條路徑節(jié)點(diǎn)的父節(jié)點(diǎn)都修改為根節(jié)點(diǎn)
        parents[v] = find(parents[v]);
    }
    return parents[v];
}

通過(guò)優(yōu)化后，與size，rank優(yōu)化進(jìn)行對(duì)比，最終得到的結(jié)果如下

可以看到，最終的效果依然非常明顯。但是依然有以下注意點(diǎn)

1. 路徑壓縮使路徑上的所有節(jié)點(diǎn)都指向根節(jié)點(diǎn)，所以實(shí)現(xiàn)成本稍高，例如有遞歸調(diào)用，會(huì)開辟更多的?？臻g

所以，基于這種問(wèn)題，還有另外2中更優(yōu)的做法，不僅能降低樹高，實(shí)現(xiàn)成本也會(huì)比路徑壓縮更低，分別為

1. 路徑分裂（Path Spliting）
2. 路徑減半（Path Halving）

路徑分裂，路徑減半的效率差不多，但都比路徑壓縮要好

路徑分裂（Path Spliting）

路徑分裂：使路徑上的每個(gè)節(jié)點(diǎn)都指向其祖父節(jié)點(diǎn)（parent的parent）

例如，下列的集合

在執(zhí)行find(1)操作時(shí)，會(huì)將1指向3,3指向5,5指向7,2指向4,4指向6,6指向7，所以最終執(zhí)行完畢后的結(jié)果如下圖

所以，可以看到，使用了路徑分裂這種優(yōu)化方案的話， 樹的高度的確是降低了，不像路徑壓縮一樣，直接將所有子節(jié)點(diǎn)平鋪開。所以拆分的成本會(huì)比路徑壓縮低一些。所以基于這種思路，最終實(shí)現(xiàn)的代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)保存下來(lái)
        int p = parents[v];
        //然后讓當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)
        parents[v] = parents[parents[v]];
        //更新節(jié)點(diǎn),重復(fù)執(zhí)行操作
        v = p;
    }
    return v;
}

通過(guò)與前面幾種優(yōu)化方案進(jìn)行對(duì)比，最終得到的比較結(jié)果如下

可以發(fā)現(xiàn)，路徑分裂方案確實(shí)進(jìn)一步優(yōu)化了性能。說(shuō)明這種路徑分裂方案是可行的，那接下來(lái)再研究路徑減半這種優(yōu)化方案。

路徑減半（Path Halving）

路徑減半：使路徑上的每隔一個(gè)節(jié)點(diǎn)就指向其祖父節(jié)點(diǎn)（parent的parent）

對(duì)比前面的路徑分裂，路徑分裂是每一個(gè)節(jié)點(diǎn)，都指向祖父節(jié)點(diǎn)，路徑減半是每隔一個(gè)節(jié)點(diǎn)就指向祖父節(jié)點(diǎn)。那究竟是什么意思呢？例如有下圖的集合

現(xiàn)在執(zhí)行find(1)操作，根據(jù)上面的定義，即執(zhí)行完find(1)后，1指向祖父節(jié)點(diǎn)，3指向祖父節(jié)點(diǎn)，5指向祖父節(jié)點(diǎn)，即3指向5,5指向7，其余元素保持不變，所以最終的結(jié)果如下圖

其實(shí)可以發(fā)現(xiàn)，這種方案對(duì)比前面的路徑分裂，效果類似。因?yàn)樽罴t優(yōu)化后的樹高，是一樣的?，F(xiàn)在已經(jīng)知道了優(yōu)化辦法，根據(jù)這種優(yōu)化辦法，最終得到的優(yōu)化代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //然后讓當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)
        parents[v] = parents[parents[v]];
        //parents[v]為祖父節(jié)點(diǎn)，祖父節(jié)點(diǎn)重復(fù)執(zhí)行操作
        v = parents[v];
    }
    return v;
}

最終通過(guò)下圖幾種優(yōu)化方案的對(duì)不，可以發(fā)現(xiàn)，路徑減半和路徑分裂的性能很接近

理論上來(lái)講，路徑減半與路徑分裂兩種算法，都非常優(yōu)秀。并且總體來(lái)講，都要由于其他優(yōu)化方案。

總結(jié)

摘自《維基百科》：https://en.wikipedia.org/wiki/Disjoint-set_data_structure

大概意思是

1. 使用路徑壓縮，分裂或者減半 + 基于rank或者size的優(yōu)化
   • 可以確保每個(gè)操作的均攤時(shí)間復(fù)雜度為O(α(n))，α(n) < 5

個(gè)人建議的搭配

1. Quick Union
2. 基于rank的優(yōu)化
3. Path Halving或者Path Spliting

自定義類型

之前的使用都是基于整型數(shù)據(jù)，如果其他自定義類型也想使用并查集，如何實(shí)現(xiàn)呢？可以參考以下方案

1. 通過(guò)一些方法，將自定義類型轉(zhuǎn)換為整型后，使用并查集（比如生成哈希值）
2. 使用鏈表+映射（Map）

為什么可以使用鏈表實(shí)現(xiàn)呢？因?yàn)椴⒉榧举|(zhì)上就是樹形結(jié)構(gòu)，只不過(guò)是通過(guò)數(shù)組來(lái)表達(dá)這種樹形結(jié)構(gòu)。然后樹形結(jié)構(gòu)中的每一條分支，都是一條鏈表。

demo下載地址

完！