6.2 Maintaining the heap property Introduction to algorithms


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
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)

Figure 6.2 The action of MAX-HEAPIFY (A, 2), where A.heap-size = 10.

T(n) ≤ T(2n/3) + Θ(1).

T(n) = O(lg n) or O(h) (a node of height h)


Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY(A, 3) on the array A = <27, 17, 3, 16, 13, 10, 1, 5, 7,12, 4, 8, 9, 0>.

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

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. 

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

-No effect. A[i]가 가장 크기 때문에 교환없이 MAX-HEAPIFY 함수가 종료된다.

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

-No effect. In this case, it is a leaf.

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 iterative control construct (a loop) instead of recursion.

public class Main
public static void main(String[] args)
int[] A = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};

(A, 1);

		for (int i=0; i < A.length; i++) System.out.print(A[i] + " ");

public static void MaxHeapify(int[] A, int i)
int l = i*2 + 1, r = l+1, largest, temp;

while (true)
if (l < A.length && A[l] > A[i]) largest = l;
else largest = i;

if (r < A.length && A[r] > A[largest]) largest = r;

if (largest != i)
temp = A[i];
A[i] = A[largest];
A[largest] = temp;

i = largest;
l = largest*2 + 1;
r = l + 1;
else break;

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω(lg n). (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.)

  • This is another obvious one.

    Let's take the leftmost path in the given heap. If we put the largest elements in the heap on that path and the smallest one at the root, MAX-HEAPIFY will need to be invoked once for each level in the heap in order to push the minimum element to the leftmost leaf. Since the heap height (and thus the leftmost path's length) is ⌊lg n⌋ (exercise 6.1-2), the worst-case running time of the procedure is Ω(lg n).