CLRS Solutions 6.2 Maintaining the heap property

 6.2-2

Staring 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?

MIN-HEAPIFY(A, i)

 l = LEFT(i)
 r = RIGHT(i)
 if l ≤ A.heap-size and A[l] < A[i]
     smallest = l
 else smallest = i
 if r ≤ A.heap-size and A[r] < A[smallest]
     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.

6.2-5

The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an interative control construct (a loop) instead of recursion.

MAX-HEAPIFY(A, i)

 while true
     l = LEFT(i)
     r = RIGHT(i)
     if l ≤ A.heap-size and A[l] > A[i]
         largest = l
     else largest = i
     if r ≤ A.heap-size and A[r] > A[largest]
         largest = r
     if largest == i
         return
     exchange A[i] with A[largest]
     i = largest

6.2-6

Show that the worst-case running time of MAX-HEAPIFY on a heap of size $n$ is $\Omega(lgn)$. (Hint: For a heap with $n$ nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a simple path from the root down to a leaf.)

Consider the heap resulting from $A$ where $A[1] = 1$ and $A[i]=2$ for $2\leqslant i \leqslant n$. Since $1$ is the smallest element of the heap, it must be swapped through each level of the heap until it is a leaf node. Since the heap has height $\lfloor lgn \rfloor$, MAX-HEAPIFY has worst-case time $\Omega(lgn)$.