The disjoint set class - Data Structures and Problem Solving Using Java - page 924

Show that, if all the union operations precede the find operations, then
the disjoint set algorithm with path compression is linear, even if the
union s are done arbitrarily. Note that the algorithm does not change;
only the performance changes.

24.9

Suppose that you want to add an extra operation, remove(x) , which
removes x from its current set and places it in its own. Show how to
modify the union/find algorithm so that the running time of a sequence
of M union , find , and remove operations is still O ( M α ( M, N )).

24.10

Prove that, if union operations are done by size and path compression
is performed, the worst-case running time is still O ( M log* N ).

24.11

Suppose that you implement partial path compression on find(i) by
changing the parent of every other node on the path from i to the root
to its grandparent (where doing so makes sense). This process is
called path halving . Prove that, if path halving is performed on the
find s and either union heuristic is used, the worst-case running time is
still O ( M log* N ).

24.12

IN PRACTICE
24.13

Implement the find operation nonrecursively. Is there a noticeable
difference in running time?

Suppose that you want to add an extra operation, deunion , which
undoes the last union operation not already undone. One way to do so
is to use union-by-rank—but a compressionless find —and use a stack
to store the old state prior to a union . A deunion can be implemented
by popping the stack to retrieve an old state.
d.

24.14

Why can't we use path compression?

e. Implement the union/find/deunion algorithm.

PROGRAMMING PROBLEMS
24.15

Write a program to determine the effects of path compression and the
various union strategies. Your program should process a long
sequence of equivalence operations, using all the strategies discussed
(including path halving, introduced in Exercise 24.12).

Implement Kruskal's algorithm.

24.16

An alternative minimum spanning tree algorithm is due to Prim [12].
It works by growing a single tree in successive stages. Start by pick-
ing any node as the root. At the start of a stage, some nodes are part of
the tree and the rest are not. In each stage, add the minimum-cost edge

24.17