Skip to content

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)$.