分離集合(disjoint set)是一種經典的資料結構,它有三類操作:
Make-set(a):生成包含一個元素a的集合S;
Union(X, Y):合并兩個集合X和Y;
Find-set(a):查找元素a所在集合S,即通過元素找集合句柄;
它非常适合用來解決集合合并與查找的問題,也常稱為并查集。
一、并查集的連結清單實作
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CMxYDNiNTOjJ2YjJ2YkNTOkNjM0IWN4QGMxYWN0MmM08CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
如上圖,并查集可以用連結清單來實作。
連結清單實作的并查集,Find-set(a)的時間複雜度是多少?
集合裡的每個元素,都指向“集合的句柄”,這樣可以使得“查找元素a所在集合S”,即Find-set(a)操作在O(1)的時間内完成。
連結清單實作的并查集,Union(X, Y)的時間複雜度是多少?
假設有集合:
S1={7,3,1,4}
S2={1,6}
合并S1和S2兩個集合,需要做兩件事情:
(1) 第一個集合的尾元素,鍊向第二個集合的頭元素(藍線1);
(2) 第二個集合的所有元素,指向第一個集合的句柄(藍線2,3);
合并完的效果是:
變成了一個更大的集合S1。
集合合并時,将短的連結清單,往長的連結清單上接,這樣變動的元素更少,這個優化叫做“權重合并”。
畫外音:實作的過程中,集合句柄要存儲元素個數,頭元素,尾元素等屬性,以友善上述操作進行。
假設每個集合的平均元素個數是n,Union(X, Y)操作的時間複雜度是O(n)。
能不能Find-set(a)與Union(X, Y)都在O(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)。
畫外音:假設集合的首個元素,代表集合句柄。
有根樹實作的并查集,Union(X, Y)的過程如何?時間複雜度是多少?
通過有根樹實作并查集,集合合并時,直接将一個集合句柄,指向另一個集合即可。
如上圖所示,S2的句柄,指向S1的句柄,集合合并完成:S2消亡,S1變為了更大的集合。
容易知道,集合合并的時間複雜度為O(1)。
會發現,集合合并之後,有根樹的高度變高了,與“權重合并”的優化思路類似,總是把節點數少的有根樹,指向節點數多的有根樹(更确切的說,是高度矮的樹,指向高度高的樹),這個優化叫做“按秩合并”。
新的問題來了,集合合并之後,不是所有元素的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)
使用并查集,非常适合解決“微信群覆寫”問題。
思路比結論重要,有收獲就是好的。
架構師之路-分享可落地的技術文章