Skip to content

6.3 Building a heap

6.3-1

Using figure 6.3 as a model, illustrate the operation of $\text{BUILD-MAX-HEAP}$ on the array $A = \langle 5, 3, 17, 10, 84, 19, 6, 22, 9 \rangle$.

$$ \begin{aligned} \langle 5, 3, 17, 10, 84, 19, 6, 22, 9 \rangle \\ \langle 5, 3, 17, 22, 84, 19, 6, 10, 9 \rangle \\ \langle 5, 3, 19, 22, 84, 17, 6, 10, 9 \rangle \\ \langle 5, 84, 19, 22, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 5, 19, 22, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 22, 19, 5, 3, 17, 6, 10, 9 \rangle \\ \langle 84, 22, 19, 10, 3, 17, 6, 5, 9 \rangle \\ \end{aligned} $$

6.3-2

Why do we want the loop index $i$ in line 2 of $\text{BUILD-MAX-HEAP}$ to decrease from $\lfloor A.length / 2 \rfloor$ to $1$ rather than increase from $1$ to $\lfloor A.length/2 \rfloor$?

Otherwise we won't be allowed to call $\text{MAX-HEAPIFY}$, since it will fail the condition of having the subtrees be max-heaps. That is, if we start with $1$, there is no guarantee that $A[2]$ and $A[3]$ are roots of max-heaps.

6.3-3

Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height $h$ in any $n$-element heap.

Let $H$ be the height of the heap.

Two subtleties to beware of:

  • Be careful not to confuse the height of a node (longest distance from a leaf) with its depth (distance from the root).
  • If the heap is not a complete binary tree (bottom level is not full), then the nodes at a given level (depth) don't all have the same height. For example, although all nodes at depth $H$ have height $0$, nodes at depth $H - 1$ can have either height $0$ or height $1$.

For a complete binary tree, it's easy to show that there are $\lceil n / 2^{h + 1}\rceil$ nodes of height $h$. But the proof for an incomplete tree is tricky and is not derived from the proof for a complete tree.

Proof

By induction on $h$.

Basis: Show that it's true for $h = 0$ (i.e., that # of leaves $\le \lceil n / 2^{h + 1} \rceil = \lceil n / 2 \rceil$ In fact, we'll show that the # of leaves $= \lceil n / 2 \rceil$.

The tree leaves (nodes at height $0$) are at depths $H$ and $H - 1$. They consist of

  • all nodes at depth $H$, and
  • the nodes at depth $H - 1$ that are not parents of depth-$H$ nodes.

Let $x$ be the number of nodes at depth $H$—that is, the number of nodes in the bottom (possibly incomplete) level.

Note that $n - x$ is odd, because the $n - x$ nodes above the bottom level form a complete binary tree, and a complete binary tree has an odd number of nodes ($1$ less than a power of $2$). Thus if $n$ is odd, $x$ is even, and if $n$ is even, $x$ is odd.

To prove the base case, we must consider separately the case in which $n$ is even ($x$ is odd) and the case in which $n$ is odd ($x$ is even). Here are two ways to do this: The first requires more cleverness, and the second requires more algebraic manipulation.

  1. First method of proving the base case:

    • If $n$ is odd, then $x$ is even, so all nodes have siblings—i.e., all internal nodes have $2$ children. Thus (see Exercise B.5-3),# of internal nodes $=$ # of leaves $- 1$. So, $n =$ # of nodes $=$ # of leaves $+$ # of internal nodes $ = 2 \cdot$ # of leaves $- 1$. Thus, # of leaves $= (n + 1) / 2$. (The latter equality holds because $n$ is odd.)
    • If $n$ is even, then $x$ is odd, and some leaf doesn't have a sibling. If we gave it a sibling, we would have $n + 1$ nodes, where $n + 1$ is odd, so the case we analyzed above would apply. Observe that we would also increase the number of leaves by $1$, since we added a node to a parent that already had a child. By the odd-node case above, # of leaves $+ 1 = \lceil (n + 1) / 2 \rceil = \lceil n / 2 \rceil + 1$. (The latter equality holds because $n$ is even.)

    In either case, # of leaves = $\lceil n / 2 \rceil$.

  2. Second method of proving the base case:
    Note that at any depth $d < H$ there are $2^d$ nodes, because all such tree levels are complete.

    • If $x$ is even, there are $x / 2$ nodes at depth $H - 1$ that are parents of depth $H$ nodes, hence $2^{H - 1} - x / 2$ nodes at depth $H - 1$ that are not parents of depth-$H$ nodes. Thus,

      $$ \begin{aligned} \text{total \# of height-$0$ nodes} & = x + 2^{H - 1} - x / 2 \\ & = 2^{H - 1} + x / 2 \\ & = (2^H + x) / 2 \\ & = \lceil (2^H + x - 1) / 2 \rceil & \text{(because $x$ is even)} \\ & = \lceil n / 2 \rceil \end{aligned} $$

      ($n = 2^H + x - 1$ because the complete tree down to depth $H - 1$ has $2^H - 1$ nodes and depth $H$ has $x$ nodes.)

    • If $x$ is odd, by an argument similar to the even case, we see that

      $$ \begin{aligned} \text{total \# of height-$0$ nodes} & = x + 2^{H - 1} - (x + 1) / 2 \\ & = 2^{H - 1} + (x - 1) / 2 \\ & = (2^H + x - 1) / 2 \\ & = n / 2 \\ & = \lceil n / 2 \rceil & \text{(because $x$ is odd $\Rightarrow n$ is even)}. \end{aligned} $$

Inductive step: Show that if it's true for height $H - 1$, it's true for $h$.

Let $n_h$ be the number of nodes at height $h$ in the $n$-node tree $T$.

Consider the tree $T'$ formed by removing the leaves of $T$. It has $n' = n - n_0$ nodes. We know from the base case that $n_0 = \lceil n / 2 \rceil$, so $n' = n - n_0 = n - \lceil n / 2 \rceil = \lfloor n / 2 \rfloor$.

Note that the nodes at height $h$ in $T$ would be at height $h - 1$ if the leaves of the tree were removed—that is, they are at height $h - 1$ in $T'$. Letting $n'_{h - 1}$ denote the number of nodes at height $h - 1$ in $T'$, we have

$$n_h = n'_{h - 1}.$$

By induction, we can bound $n'_{h - 1}$:

$$n_h = n'_{h - 1} \le \lceil n' / 2^h \rceil = \big\lceil\lfloor n / 2 \rfloor / 2^h \big\rceil \le \lceil (n / 2) / 2^h \rceil = \lceil n / 2^{h + 1} \rceil.$$

Alternative solution

An alternative solution relies on four facts:

  1. Every node not on the unique simple path from the last leaf to the root is the root of a complete binary subtree.
  2. A node that is the root of a complete binary subtree and has height $h$ is the ancestor of $2^h$ leaves.
  3. By Exercise 6.1-7, an n-element heap has $\lceil n / 2 \rceil$ leaves.
  4. For nonnegative reals $a$ and $b$, we have $\lceil a \rceil \cdot b \ge \lceil ab \rceil$.

The proof is by contradiction. Assume that an $n$-element heap contains at least $\lceil n / 2^{h + 1} \rceil + 1$ nodes of height $h$. Exactly one node of height $h$ is on the unique simple path from the last leaf to the root, and the subtree rooted at this node has at least one leaf (that being the last leaf). All other nodes of height $h$, of which the heap contains at least $\lceil n / 2^{h + 1} \rceil$, are the roots of complete binary subtrees, and each such node is the root of a subtree with $2^h$ leaves. Moreover, each subtree whose root is at height $h$ is disjoint. Therefore, the number of leaves in the entire heap is at least

$$ \begin{aligned} \Big\lceil \frac{n}{2^{h + 1}} \Big\rceil \cdot 2^h + 1 & \ge \Big\lceil \frac{n}{2^{h + 1}} \cdot 2^h \Big\rceil + 1 \\ & = \Big\lceil \frac{n}{2} \Big\rceil + 1, \end{aligned} $$

which contradicts the property that an $n$-element heap has $\lceil n / 2 \rceil$ leaves.