Revision as of 00:11, 4 October 2004 edit Dcoetzee (talk \| contribs) 37,529 edits →Disjoint-set forests: Reword a bit ← Previous edit		Revision as of 00:20, 4 October 2004 edit undo Dcoetzee (talk \| contribs) 37,529 edits A reference and a note Next edit →
Line 14: 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, called the ''weighted union heuristic''. This also requires keeping track of the length of each list as we perform operations to be efficient. Using this, a sequence of ''m'' '''Make-Set''', '''Union''', and '''Find''' operations on ''n'' elements requires O(''m'' + ''n''log ''n'') time. To make any further progress, we need to start over with a different data structure. == Disjoint-set forests == Line 47: * Chapter 21, ''Introduction to Algorithms'', 2nd ed. Cormen, Leiserson, Rivest, Stein. ISBN 0262032937. == External links == * [http://research.compaq.com/SRC/zeus/unionfind.html Compaq Research: Zeus: Animation of Union-Find Algorithms]

Disjoint-set data structure: Difference between revisions