§ intuition for correctness of rank:

Assume that we had to re-point pointers of all our children to the new root when we decide to make another node the root. That is, we would have:

void mkroot(int newroot, int prevroot) {   for (int child : children[prevroot] {        parent[child] = newroot;   }   parent[prevroot] = newroot];   children[prevroot] = {}; // this has no children anymore}

• In this setting, we ought to make the smaller subtree the prevrootand the larger subtree the newroot: It is better to loop over fewer children.

• When we perform the rank based union, we are using the same heuristic , even though we don't actually loop over all our children.