Disjoint Set Data Structure: Union-Find

The problem

We want to maintain a set of disjoint sets, in which elements are fixed. Only union is supported, while spliting is not. Sepcifically, we support following three operations.

• MakeSet(u)
• Find(u)
• Union(u,v)

Let donote the fixed set of elements, whose size is . Generally, we want to estimate the total time of a sequence of operations, in which the first operation is MakeSet for each element.

Linked-list

We can represent each set by a linked list, with each element additionally pointing to its head.
The worst-case time for Union is #card=math&code=O%28n%29), and we can find a sequence of operations which needs #card=math&code=O%28n%5E2%29) time in total.

a weighted-union heuristic

We can improve it by a little trick. In the Union operation, we can rename the small set (say B) to the larger set (say A), i.e. make all the elements of B point to the head of A. The worst-case time of Union is stilll #card=math&code=O%28n%29), while its amortized time becomes #card=math&code=O%28%5Clog%20n%29).

	worst-case	amortized
MakeSet	#card=math&code=O%281%29)	#card=math&code=O%281%29)
Find	#card=math&code=O%281%29)	#card=math&code=O%281%29)
Union	#card=math&code=O%28n%29)	#card=math&code=O%28%5Clog%20n%29)
Total	#card=math&code=O%28m%5Clog%20n%29)	-

Forest

With rooted trees, Union costs #card=math&code=O%281%29), while Find may cost O(n) in worst-case. It can also be improved to #card=math&code=O%28%5Clog%20n%29) using the same weighted-union heuristic: Union-by-rank. Actually, Union-by-size works as well. The total time is also #card=math&code=O%28m%5Clog%20n%29)
Using another heuristic “path compression”, we can amortize the time of Find and Union to )#card=math&code=O%28%5Calpha%28n%29%29), which results )#card=math&code=O%28m%5Calpha%28n%29%29) time in total.

	no heuristic	weighted-union	both(amortized)
MakeSet	#card=math&code=O%281%29)	#card=math&code=O%281%29)	#card=math&code=O%281%29)
Find	#card=math&code=O%28n%29)	#card=math&code=O%28%5Clog%20n%29)	)#card=math&code=O%28%5Calpha%28n%29%29)
Union	#card=math&code=O%281%29)	#card=math&code=O%281%29)	)#card=math&code=O%28%5Calpha%28n%29%29)
Total	#card=math&code=O%28mn%29)	#card=math&code=O%28m%5Clog%20n%29)	)#card=math&code=O%28m%5Calpha%28n%29%29)