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