Given the following code: LEFT(i) return 2i RIGHT(i) return 2i + 1 MaxHeapify(A, i) l = LEFT(i); r = RIGHT(i); if l A[i] largest =

Given the following code:

LEFT(i)

return 2i

RIGHT(i)

return 2i + 1

MaxHeapify(A, i)

l = LEFT(i);

r = RIGHT(i);

if l <= A.heap-size and A[l] > A[i]

largest = l;

else

largest = i;

if l <= A.heap-size and A[r] > A[largest]

largest = r;

if largest != i

exchange A[i] with A[largest]

MaxHeapify(A, largest);

BuildMaxHeap(A)

A.heap-size = A.length

for i = floor(A.length/2) downto 1

MaxHeapify(A, i)

a. What is the effect of calling MaxHeapify(A,i) where i < A.heap-size/2 ?

b. If we modify the for loop in BuildMaxHeap(A) to increase from 1 to floor(A.length/2) rather than decrease from floor(A.length/2) to 1, would the algorithm work?

c. Rewrite MaxHeapify(A, i) that uses a loop instead of recursion.