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:

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. It is very easy to find out that the $\text{MAX-HEAP-INSERT}$ operation for each iteration takes $\Theta(\log i)$ time, therefore the total time complexity is the sum of the individual complexities for $i$ from $2$ to $n$, which is : $\Theta(\log 2) + \Theta(\log 3) + \dots + \Theta(\log n) = \Theta(\log n!) $. By using Stirling's approximation, $\Theta (\log n!) \approx \Theta(n\log n)$, so the overall complexity is $\Theta(n\log⁡ n)$.