4. 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 num The following shows a collection of sets containing the numbers 1 through 14, without the weight array filled in 10 11 12 13 14 up 10 1 weight a) b) Draw a picture of the uptrees represented by the data in the up array shown above. Now, draw a new set of uptrees to show the results of executing union (find (1), find (9); find (11)); 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. 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 c) 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 (assuming you are always passed roots as parameters)? N = total # of elements in all sets. (no explanation required) 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) e)