For HEAPSORT codes below

Heapsort(A)

{

Build-MAX-Heap(A);

for (i = A.length downto 2)

{

Swap(A[1], A[i]);

A.heap_size= A.heap_size - 1;

MAX-Heapify(A, 1);

}

}

(b) If we replace MAX-Heapify(A, 1) with Build-MAX-Heap(A), what is the number of required swap operations when heapsort the array A? Explain your reason.

(c) (Does the asymptotic upper bound of Heapsort increase from O(nlgn) to O( 2 )? Why? (Hint: compare the number of swap operations before and after the change for the worst case).