Suppose we implement partial path compression on find(i) by making every other node on the path from i to the root link to its grandparent (where this makes sense). This is known as path halving.

a. Write a procedure to do this.

b. Prove that if path halving is performed on the finds and either union-by-height or union-by-size is used, the worst-case running time is O(Mα(M,N)).