Suppose a collection of foods must be divided into groups such as fruit, vegetables, and sweets. Each food belongs to one group, and no two groups overlap. A disjoint set maintains such a partition while allowing groups to be merged. The collection of possible elements is the universe. section 5.0 section 5.2
Initialize every element in its own singleton partition. `findPartition(x)` identifies the partition containing `x`; its returned identifier need not mean anything outside the data structure. `areDisjoint(x, y)` checks whether two elements belong to different partitions, and `merge(x, y)` combines their partitions. Merges can also connect elements indirectly: if two pairs share an element, all three elements end up together. section 5.3
Choose an implementation according to how often groups change:
- Map each element to its partition. Finding a partition is constant-time, but merging requires updating the elements of one partition and can take linear time. This may suit a read-heavy workload with rare merges. section 5.4.1 section 5.5 section 5.5.2
- Represent each partition as a tree. `findPartition` follows parents to the root; `merge` finds two roots and makes one the parent of the other. Operations average logarithmic time but can still take linear time in the worst case. section 5.5.2
- Improve the trees by attaching the smaller one beneath the larger one and compressing paths during `findPartition`. Store each element’s parent and its tree’s size; the resulting operations are described as quasi-constant-time. section 5.6.2 section 5.8
Listing 5.10 Tree-with-heuristics solution, merge
function merge(elem1, elem2) #1
r1 ← this.findPartition(elem1) #2
r2 ← this.findPartition(elem2) #2
if r1 == r2 then #3
return false
info1 ← this.parentsMap[r1] #4
info2 ← this.parentsMap[r2]
if info1.rank >= info2.rank then #5
info2.root ← info1.root; #6
info1.rank += info2.rank; #7
else
info1.root ← info2.root; #6
info2.rank += info1.rank; #7
return true
The merge pseudocode shows how comparing tree sizes selects a root and updates the combined size without revisiting every element. section 5.6.2
Connected components of an undirected graph
Start with one partition per vertex, then merge the endpoints of every edge. When all edges have been scanned, each partition is a connected component. This procedure does not compute strongly connected components of a directed graph. A related use is Kruskal’s minimum-spanning-tree algorithm, which considers edges by increasing weight and merges only endpoints in different partitions. section 5.7.1 section 5.7.2
