# 6.2 Maintaining the heap property

## 6.2-1

Using figure 6.2 as a model, illustrate the operation of $\text{MAX-HEAPIFY}(A, 3)$ on the array $A = \langle 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0 \rangle$.

\begin{aligned} \langle 27, 17, 3, 16, 13, 10,1, 5, 7, 12, 4, 8, 9, 0 \rangle \\ \langle 27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0 \rangle \\ \langle 27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0 \rangle \\ \end{aligned}

## 6.2-2

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

 1 2 3 4 5 6 7 8 9 10 11 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-3

What is the effect of calling $\text{MAX-HEAPIFY}(A, i)$ when the element $A[i]$ is larger than its children?

No effect. The comparisons are carried out, $A[i]$ is found to be largest and the procedure just returns.

## 6.2-4

What is the effect of calling $\text{MAX-HEAPIFY}(A, i)$ for $i > A.heap\text-size / 2$?

No effect. In that case, it is a leaf. Both $\text{LEFT}$ and $\text{RIGHT}$ return values that fail the comparison with the heap size and $i$ is stored in largest. Afterwards the procedure just returns.

## 6.2-5

The code for $\text{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 $\text{MAX-HEAPIFY}$ that uses an iterative control construct (a loop) instead of recursion.

 1 2 3 4 5 6 7 8 9 10 11 12 13 MAX-HEAPIFY(A, i) while true left = LEFT(i) right = RIGHT(i) if left < A.heap-size and A.nodes[left] > A.nodes[i] largest = left else largest = i if right < A.heap-size and A.nodes[right] > A.nodes[largest] largest = right if largest == i return exchange A.nodes[i] with A.nodes[largest] i = largest

## 6.2-6

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

If you put a value at the root that is less than every value in the left and right subtrees, then $\text{MAX-HEAPIFY}$ will be called recursively until a leaf is reached. To make the recursive calls traverse the longest path to a leaf, choose values that make $\text{MAX-HEAPIFY}$ always recurse on the left child. It follows the left branch when the left child is greater than or equal to the right child, so putting $0$ at the root and $1$ at all the other nodes, for example, will accomplish that. With such values, $\text{MAX-HEAPIFY}$ will be called $h$ times (where $h$ is the heap height, which is the number of edges in the longest path from the root to a leaf), so its running time will be $\Theta(h)$ (since each call does $\Theta(1)$ work), which is $\Theta(\lg n)$. Since we have a case in which $\text{MAX-HEAPIFY}$'s running time is $\Theta(\lg n)$, its worst-case running time is $\Omega(\lg n)$.