A crossover between Floyd’s and Williams’s methods for constructing a heap is a method in which an empty position occupied by an element is moved down to the bottom of the tree and then the element is...

A crossover between Floyd’s and Williams’s methods for constructing a heap is a method in which an empty position occupied by an element is moved down to the bottom of the tree and then the element is moved up the tree, as in Williams’s method, from the position that was just moved down. A pseudocode of this function is as follows:

It has been shown that this algorithm requires 1.65n comparisons in the average case (McDiarmid and Reed, 1989). Show changes in the array [2 8 6 1 10 15 3 12 11] during execution of the algorithm. What is the worst case?