6-1 Building a heap using insertion

One way to build a heap is by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the procedure BUILD-MAX-HEAP' on the facing page. It assumes that the objects being inserted are just the heap elements.

BUILD-MAX-HEAP'(A,n)
  A.heap-size = 1
  for i = 2 to n
      MAX-HEAP-INSERT(A,A[i],n)

a. Do the procedures BUILD-MAX-HEAP and 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, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build an $n$-element heap.

a

No. For a countereaxmple, $A = <1,2,3>$.

BUILD-MAX-HEAP returns $A = <3,2,1>$.

While BUILD-MAX-HEAP' returns $A = <3,1,2>$.

b

In the worst case, MAX-HEAP-INSERT(A,A[i],n) require $\Theta(\lg i)$, then we have BUILD-MAX-HEAP' requires:

$$ \begin{aligned} T(n) & = \sum_{i=2}^{n}\Theta(\lg i)\cr & = \Theta(\lg \prod_{i=2}^{n}i)\cr & = \Theta(\lg (n!))\cr & = \Theta(n\lg n)\cr \end{aligned} $$