6-1 Building a heap using insertion

We can build a heap by repeatedly calling \(\text{MAX-HEAP-INSERT}\) to insert the elements into the heap. Consider the following variation of the \(\text{BUILD-MAX-HEAP}\) procedure:

C++
1
2
3
4
BUILD-MAX-HEAP'(A)
    A.heap-size = 1
    for i = 2 to A.length
        MAX-HEAP-INSERT(A, A[i])

a. Do the procedures \(\text{BUILD-MAX-HEAP}\) and \(\text{BUILD-MAX-HEAP}'\) always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.

b. Show that in the worst case, \(\text{BUILD-MAX-HEAP}'\) requires \(\Theta(n\lg n)\) time to build a \(n\)-element heap.

a. Consider the following counterexample.

  • Input array \(A = \langle 1, 2, 3 \rangle\):
  • \(\text{BUILD-MAX-HEAP}(A)\): \(A = \langle 3, 2, 1 \rangle\).
  • \(\text{BUILD-MAX-HEAP}'(A)\): \(A = \langle 3, 1, 2 \rangle\).

b. Each insert step takes at most \(O(\lg n)\), since we are doing it \(n\) times, we get a bound on the runtime of \(O(n\lg n)\).

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