Exercise 6.2.2

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?

  l = LEFT(i)
  r = RIGHT(i)
  if l ≤ A.heap-size and A[l] < A[i]
      smallest = l
      smallest = i
  if r ≤ A.heap-size and A[r] < A[i]
      smallest = r
  if smallest ≠ i
      exchange A[i] with A[smallest]
      MIN-HEAPIFY(A, smallest)

The running time is the same. Actually, the algorithm is the same with the exceptions of two comparisons and some names.