Disjoint-set data structure: Difference between revisions

Revision as of 23:55, 3 October 2004

Revision as of 00:07, 4 October 2004

Line 10:

Perhaps the simplest approach to creating a disjoint-set data structure is to create a [[linked list]] for each group. We choose the element at the head of the list as the representative.

'''Make-Set''' is obvious, creating a list of one element. '''Union''' simply appends the two lists, a constant-time operation. Unfortunately, it seems that '''Find''' requires [[Big-O notation|OΩ]](n) or linear time with this approach.

We can avoid this by including in each linked list node a pointer to the head of the list; then '''Find''' takes constant time. However, we've now ruined the time of '''Union''', which has to go through the elements of the list being appended to make them point to the head of the new combined list., requiring [[Big-O notation|Ω]](n) time.

We can ameliorate this by always appending the smaller list to the longer, butcalled eventhe in''weighted union heuristic''. Using this, casea sequence of ''m'' '''Make-Set''', '''Union''', canand take'''Find''' Ωoperations on ''n'' elements requires O(''m'' + ''n''log ''n'') time on average. To solvemake thisany further progress, we need to start over with a different data structure.

== Disjoint-set forests ==