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

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
        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 \(\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.)

Consider the heap resulting from \(A\) where \(A[1] = 1\) and \(A[i] = 2\) for \(2 \le i \le 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 \lg n\rfloor\), \(\text{MAX-HEAPIFY}\) has worst-case time \(\Omega(\lg n)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用