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:

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. The procedures $\text{BUILD-MAX-HEAP}$ and $\text{BUILD-MAX-HEAP}'$ do not always create the same heap when run on the same input array.

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. An upper bound of $O(n\lg n)$ time follows immediately from there being $n - 1$ calls to $\text{MAX-HEAP-INSERT}$, each taking $O(\lg n)$ time. For a lower bound of $\Omega(n\lg n)$, consider the case in which the input array is given in strictly increasing order. Each call to $\text{MAX-HEAP-INSERT}$ causes $\text{HEAP-INCREASE-KEY}$ to go all the way up to the root. Since the depth of node $i$ is $\lfloor \lg i \rfloor$, the total time is

$$ \begin{aligned} \sum_{i = 1}^n \Theta(\lfloor \lg i \rfloor) & \ge \sum_{i = \lceil n / 2 \rceil}^n \Theta(\lfloor \lg \lceil n / 2 \rceil\rfloor) \\ & \ge \sum_{i = \lceil n / 2 \rceil}^n \Theta(\lfloor \lg (n / 2) \rfloor) \\ & = \sum_{i = \lceil n / 2 \rceil}^n \Theta(\lfloor \lg n - 1 \rfloor) \\ & \ge n / 2 \cdot \Theta(\lg n) \\ & = \Omega(n\lg n). \end{aligned} $$

In the worst case, therefore, $\text{BUILD-MAX-HEAP}'$ requires $\Theta(n\lg n)$ time to build an $n$-element heap.