For set$-$union$-$find data structure, we saw that total number of head pointer changes during all the union operations is O$($n log n$).$ Here, we try to improve upon this bound.

We are going to maintain two level disjoint set data structure. At the lower level this is a disjoint set data structure on V $.$ At the upper level, this is a disjoint set data structure on V $$ V $.$ The change is that while doing unon at the lower level, if both the lists are $$ log n$,$ then the union operation is performed at the upper level. At any point, after the union, if a list at lower level grows $$ log n$,$ then the head element of that list is inserted into the upper level structure and a part of V $.$

At the lower level structure, head element of each linked list maintains $$size$$ of the list and also a field called $$upptr$.$ This points to the copy of head element of this list in upper level structure $($if one exists$).$

For union$($x$,$ y$),$ we do as follows: Let s $=$ find$($x$)$ and t $=$ find$($y$).$ If s and t both have non null upptr, then let s$=$ upptr$($s$)$ and t$=$ upptr$($t$),$ and then perform union$($s$,$t$)$ in the upper level structure. Otherwise, assume wlog that size$($s$)$ size$($t$).$ Perform union$($s$,$ t$),$ If size$($s$)$ becomes $$ logn and upptr$($s$)$ is null, then insert a new singleton set $\{$s$\}$ in upper level structure. Set s$=$ upptr$($s$).$ Both s$$ and s hold the same vertex.

To determine whether find$($x$)$ is the same as find$($y$)$ or not, we first check if head$($x$)$ is same as head$($y$)$ If yes, then the answer is yes. If not, then we check if head$($upptr$($head$($x$)))$ is the same as head$($upptr$($head$($y$))).$ If so$,$ the answer is yes, else the answer is no$.$

$($a$)$ Show that $|$V $|$ n$/$ log n$.$

$($b$)$ Show that any element changes its head pointer no more than log log n times at the lower level.

$($c$)$ Show that any element in V $$ will change its head pointer at most log n times.

$($d$)$ Show that total number of head pointer changes across all unions in upper and lower levels is O$($n log log n$).$

This improves O$($m $+$ n log n$)$ bound that we saw in the class to O$($m $+$ n log log n$).$ Any ideas if further improvement can be made?