Question

Please answer full question thoroughly (A- D) showing detailed work. SUBMIT ORIGINAL work and ensure it is correct for thumbs up.

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

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

c) The code for MAX-HEAPIFYis 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.

d)  Show that there are at most nodes of height h in any n-element heap.

Answer 1

a) When the element A[i] is larger than its children, just return to the calling function.

b) Under the given condition, i>A.heap-size/2, the node is a leaf node.

c) Below is the pseudo code:

MIN-HEAPIFY(A, i):
        while i ≤ heap-size[A]:
                l <- LEFT(i)
                r <- RIGHT(i)
                largest <- i
                if l ≤ heap-size[A] and A[l] > A[i]:
                        then largest <- l
                if r ≤ heap-size[A] and A[r] > A[largest]:
                        then largest <- r
                if largest ≠ i:
                        then swap(A[i], A[largest])
                                 i = largest
                else break

d) The question should be "Show that there are at most ⌈n/2^h+1⌉ nodes of height h in any n-element heap.

Base: Height h=0. The number of leaves is ⌈n/2⌉=⌈n/2⁰⁺¹⌉.

Step: Let's assume it holds for nodes of height h−1. Let's take a tree and remove all it's leaves. We get a new tree with n−⌈n/2⌉=⌊n/2⌋ elements. Note that the nodes with height h in the old tree have height h−1 in the new one.

We will calculate the number of such nodes in the new tree. By the inductive assumption we have that T, the number of nodes with height h−1 in the new tree, is:

T=⌈⌊n/2⌋/2^h−1+1⌉<⌈(n/2)/2^h⌉=⌈n2^h+1⌉

As mentioned, this is also the number of nodes with height h in the old tree.