Disjoint Sets

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 the node has no parent$).$ The weight array stores the number of items in a set $($its weight$)$ if the node is the root $($representative node$)$ of a set. $($If a node is not a root the contents of its location in the weight array are undefined $-$ we don't care what value it holds, it can be zero or any other number.$)$

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

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

b$)$ Now, draw a new set of uptrees to show the results of executing:

union$($find$(1),$ find$(11))$;

find $(9)$ ;

Regardless of how the trees from part a$)$ were constructed, here assume that find uses path compression and that union uses union$-$by$-$size $($aka union by weight$).$ In case of ties in size, always make the higher numbered root point to the lower numbered one. Unioning a set with itself does nothing.

c$)$ Update the up and weight arrays at the top of the previous page to reflect the picture after part b$).$ That is$,$ fill in the contents of the weight array and update the contents of the up array.

d$)$ What is the worst case big$-$O running time of a single find operation if union by size $($aka union by weight$)$ and path compression are used $?N=$ total # of elements in all sets. $($no explanation required$)$

e$)$ Assuming that you are using union by size and path compression, how long would we expect a sequence of $N-1$ union operations and $J$ find operations to take? $(N=$ total # of elements in all sets$)$ Express your answer in terms of big$-$O$,($no explanation required$)$