一分鐘說(shuō)清楚并查集
分離集合(disjoint set)是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它有三類(lèi)操作：
- Make-set(a)：生成包含一個(gè)元素a的集合S;
- Union(X, Y)：合并兩個(gè)集合X和Y;
- Find-set(a)：查找元素a所在集合S，即通過(guò)元素找集合句柄;
它非常適合用來(lái)解決集合合并與查找的問(wèn)題，也常稱(chēng)為并查集。
一、并查集的鏈表實(shí)現(xiàn)
如上圖，并查集可以用鏈表來(lái)實(shí)現(xiàn)。
(1) 鏈表實(shí)現(xiàn)的并查集，F(xiàn)ind-set(a)的時(shí)間復(fù)雜度是多少?
集合里的每個(gè)元素，都指向“集合的句柄”，這樣可以使得“查找元素a所在集合S”，即Find-set(a)操作在O(1)的時(shí)間內(nèi)完成。
(2) 鏈表實(shí)現(xiàn)的并查集，Union(X, Y)的時(shí)間復(fù)雜度是多少?
假設(shè)有集合：
- S1={7,3,1,4}
- S2={1,6}
合并S1和S2兩個(gè)集合，需要做兩件事情：
- ***個(gè)集合的尾元素，鏈向第二個(gè)集合的頭元素(藍(lán)線1);
- 第二個(gè)集合的所有元素，指向***個(gè)集合的句柄(藍(lán)線2,3);
合并完的效果是：
變成了一個(gè)更大的集合S1。
集合合并時(shí)，將短的鏈表，往長(zhǎng)的鏈表上接，這樣變動(dòng)的元素更少，這個(gè)優(yōu)化叫做“加權(quán)合并”。
畫(huà)外音：實(shí)現(xiàn)的過(guò)程中，集合句柄要存儲(chǔ)元素個(gè)數(shù)，頭元素，尾元素等屬性，以方便上述操作進(jìn)行。
假設(shè)每個(gè)集合的平均元素個(gè)數(shù)是n，Union(X, Y)操作的時(shí)間復(fù)雜度是O(n)。
(3) 能不能Find-set(a)與Union(X, Y)都在O(1)的時(shí)間內(nèi)完成呢?
可以，這就引發(fā)了并查集的第二種實(shí)現(xiàn)方法。
二、并查集的有根樹(shù)實(shí)現(xiàn)
(1) 什么是有根樹(shù)，和普通的樹(shù)有什么不同?
常用的set，就是用普通的二叉樹(shù)實(shí)現(xiàn)的，其元素的數(shù)據(jù)結(jié)構(gòu)是：
- element{
- int data;
- element* left;
- element* right;
- }
通過(guò)左指針與右指針，父親節(jié)點(diǎn)指向兒子節(jié)點(diǎn)。
而有根樹(shù)，其元素的數(shù)據(jù)結(jié)構(gòu)是：
- element{
- int data;
- element* parent;
- }
通過(guò)兒子節(jié)點(diǎn)，指向父親節(jié)點(diǎn)。
假設(shè)有集合：
- S1={7,3,1,4}
- S2={1,6}
通過(guò)如果通過(guò)有根樹(shù)表示，可能是這樣的：
所有的元素，都通過(guò)parent指針指向集合句柄，所有元素的Find-set(a)的時(shí)間復(fù)雜度也是O(1)。
畫(huà)外音：假設(shè)集合的***元素，代表集合句柄。
(2) 有根樹(shù)實(shí)現(xiàn)的并查集，Union(X, Y)的過(guò)程如何?時(shí)間復(fù)雜度是多少?
通過(guò)有根樹(shù)實(shí)現(xiàn)并查集，集合合并時(shí)，直接將一個(gè)集合句柄，指向另一個(gè)集合即可。
如上圖所示，S2的句柄，指向S1的句柄，集合合并完成：S2消亡，S1變?yōu)榱烁蟮募稀?/p>
容易知道，集合合并的時(shí)間復(fù)雜度為O(1)。
會(huì)發(fā)現(xiàn)，集合合并之后，有根樹(shù)的高度變高了，與“加權(quán)合并”的優(yōu)化思路類(lèi)似，總是把節(jié)點(diǎn)數(shù)少的有根樹(shù)，指向節(jié)點(diǎn)數(shù)多的有根樹(shù)(更確切的說(shuō)，是高度矮的樹(shù)，指向高度高的樹(shù))，這個(gè)優(yōu)化叫做“按秩合并”。
(3) 新的問(wèn)題來(lái)了，集合合并之后，不是所有元素的Find-set(a)操作都是O(1)了，怎么辦?
如圖S1與S2合并后的新S1，***“通過(guò)元素6來(lái)找新S1的句柄”，不能在O(1)的時(shí)間內(nèi)完成了，需要兩次操作。
但為了讓未來(lái)“通過(guò)元素6來(lái)找新S1的句柄”的操作能夠在O(1)的時(shí)間內(nèi)完成，在***進(jìn)行Find-set(“6”)時(shí)，就要將元素6“尋根”路徑上的所有元素，都指向集合句柄，如下圖。
某個(gè)元素如果不直接指向集合句柄，***Find-set(a)操作的過(guò)程中，會(huì)將該路徑上的所有元素都直接指向句柄，這個(gè)優(yōu)化叫做“路徑壓縮”。
畫(huà)外音：路徑上的元素第二次執(zhí)行Find-set(a)時(shí)，時(shí)間復(fù)雜度就是O(1)了。
實(shí)施“路徑壓縮”優(yōu)化之后，F(xiàn)ind-set的平均時(shí)間復(fù)雜度仍是O(1)。
結(jié)論
通過(guò)鏈表實(shí)現(xiàn)并查集：
- Find-set的時(shí)間復(fù)雜度，是O(1)常數(shù)時(shí)間
- Union的時(shí)間復(fù)雜度，是集合平均元素個(gè)數(shù)，即線性時(shí)間
畫(huà)外音：別忘了“加權(quán)合并”優(yōu)化。
通過(guò)有根樹(shù)實(shí)現(xiàn)并查集：
- Union的時(shí)間復(fù)雜度，是O(1)常數(shù)時(shí)間
- Find-set的時(shí)間復(fù)雜度，通過(guò)“按秩合并”與“路徑壓縮”優(yōu)化后，平均時(shí)間復(fù)雜度也是O(1)
使用并查集，非常適合解決“微信群覆蓋”問(wèn)題。
思路比結(jié)論重要，有收獲就是好的。
【本文為51CTO專(zhuān)欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
