The uptrees used to represent sets in the union-find algorithm can be stored in two n-element arrays. The up array stores the parent of each node (or -1 if it has no parent). The weight array stores the number of items in a set if the node is the representative node of a set (else the weight entry for the node does not matter and can be anything).

The following shows a collection of sets containing the numbers 1 through 12, without the weight array filled in:

up -1 10 -1 9 1 1 11 -1 7 11 -1 1

weight

1 2 3 4 5 6 7 8 9 10 11 12

a) Draw a picture of the uptrees represented by the data in the up array shown above.

b) Fill in the weight array above so that all entries that need to be correct are correct.

c) Suppose we did not keep the weight array updated as operations are performed. As you did in part (a), the algorithm could compute weights as needed. Would this asymptotically slow down find operations that use path compression?