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

Pennies are used
like a potential
function. The total
number of pennies
is the total time.

deposit an imaginary penny in each node on the path. This is strictly an
accounting gimmick that is not part of the program. It is somewhat equivalent
to the use of a potential function in the amortized analysis for splay trees and
skew heaps. When the algorithm has finished, we collect all the coins that
have been deposited to determine the total time.

As a further accounting gimmick, we deposit both U.S. and Canadian
pennies. We show that, during execution of the algorithm, we can deposit only
a certain number of U.S. pennies during each find operation (regardless of
how many nodes there are). We will also show that we can deposit only a cer-
tain number of Canadian pennies to each node (regardless of how many find s
there are). Adding these two totals gives a bound on the total number of pen-
nies that can be deposited.
We now sketch our accounting scheme in more detail. We begin by
dividing the nodes by their ranks. We then divide the ranks into rank groups.
On each find , we deposit some U.S. pennies in a general kitty and some
Canadian pennies in specific nodes. To compute the total number of Cana-
dian pennies deposited, we compute the deposits per node. By summing all
the deposits for each node in rank r, we get the total deposits per rank r .
Then we sum all the deposits for each rank r in group g and thereby obtain
the total deposits for each rank group g . Finally, we sum all the deposits for
each rank group g to obtain the total number of Canadian pennies deposited
in the forest. Adding that total to the number of U.S. pennies in the kitty
gives us the answer.

We have both U.S.
and Canadian
pennies. Canadian
pennies account for
the first few times a
node is com-
pressed; U.S.
pennies account
for later com-
pressions or
noncompressions.

As mentioned previously, we partition the ranks into groups. Rank r goes
into group G ( r ), and G is to be determined later (to balance the U.S. and
Canadian deposits). The largest rank in any rank group g is F ( g ), where
F = G -1 is the inverse of G . The number of ranks in any rank group, g > 0, is
thus F ( g ) - F ( g - 1). Clearly, G ( N ) is a very loose upper bound on the largest
rank group. Suppose that we partitioned the ranks as shown in Figure 24.22.
In this case, The largest rank in group g is F ( g ) = g 2 . Also,
observe that group g > 0 contains ranks F ( g - 1) + 1 through F ( g ). This for-
mula does not apply for rank group 0, so for convenience we ensure that rank
group 0 contains only elements of rank 0. Note that the groups comprise con-
secutive ranks.
As mentioned earlier in the chapter, each union instruction takes constant
time, so long as each root keeps track of its rank. Thus union operations are
essentially free, as far as this proof goes.

Ranks are parti-
tioned into groups.
The actual groups
are determined at
the end of the
proof. Group 0 has
only rank 0.

Gr () = r .

Each find operation takes time proportional to the number of nodes on the
path from the node representing the accessed item i to the root. We thus
deposit one penny for each vertex on the path. If that is all we do, however, we
cannot expect much of a bound because we are not taking advantage of path

When a node is
compressed, its
new parent will
have a higher rank
than its old parent.