Weighted union

Home > Computer Science > Algorithms and data structures > Disjoint Set Union > Weighted union

In this implementation, we maintain the size of each set and always merge the smaller set into the larger set. This guarantees that the height of the resulting tree is at most log(n), where n is the number of elements. The time complexity of this implementation is O(alpha(n)).