Skip to content

6.1 Heaps

6.1-1

What are the minimum and maximum numbers of elements in a heap of height $h$?

Since a heap is an almost-complete binary tree (complete at all levels except possibly the lowest), it has at most $2^{h + 1} - 1$ elements (if it is complete) and at least $2^h - 1 + 1 = 2^h$ elements (if the lowest level has just $1$ element and the other levels are complete).

6.1-2

Show that an $n$-element heap has height $\lfloor \lg n \rfloor$.

Given an $n$-element heap of height $h$, we know from Exercise 6.1-1 that

$$2^h \le n \le 2^{h + 1} - 1 < 2^{h + 1}.$$

Thus, $h \le \lg n < h + 1$. Since $h$ is an integer, $h = \lfloor \lg n \rfloor$ (by definition of $\lfloor \rfloor$).

6.1-3

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occuring anywhere in the subtree.

Assume the claim is falseā€”i.e., that there is a subtree whose root is not the largest element in the subtree. Then the maximum element is somewhere else in the subtree, possibly even at more than one location. Let $m$ be the index at which the maximum appears (the lowest such index if the maximum appears more than once). Since the maximum is not at the root of the subtree, node $m$ has a parent. Since the parent of a node has a lower index than the node, and $m$ was chosen to be the smallest index of the maximum value, $A[\text{PARENT}(m)] < A[m]$. But by the maxheap property, we must have $A[\text{PARENT}(m)] \ge A[m]$. So our assumption is false, and the claim is true.

6.1-4

Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

In any of the leaves, that is, elements with index $\lfloor n / 2 \rfloor + 1$ (see exercise 6.1-7), that is, in the second half of the heap array.

6.1-5

Is an array that is in sorted order a min-heap?

Yes. For any index $i$, both $\text{LEFT}(i)$ and $\text{RIGHT}(i)$ are larger and thus the elements indexed by them are greater or equal to $A[i]$ (because the array is sorted.)

6.1-6

Is the array with values $\langle 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 \rangle$ a max-heap?

No. Since $\text{PARENT}(7)$ is $6$ in the array. This violates the max-heap property.

6.1-7

Show that, with the array representation for sorting an $n$-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n$.

Let's take the left child of the node indexed by $\lfloor n / 2 \rfloor + 1$.

$$ \begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & > 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned} $$

Since the index of the left child is larger than the number of elements in the heap, the node doesn't have childrens and thus is a leaf. Same goes for all nodes with larger indices.

Note that if we take element indexed by $\lfloor n / 2 \rfloor$, it will not be a leaf. In case of even number of nodes, it will have a left child with index $n$ and in the case of odd number of nodes, it will have a left child with index $n - 1$ and a right child with index $n$.

This makes the number of leaves in a heap of size $n$ equal to $\lceil n / 2 \rceil$.