6.1 Heaps

6.1-1

The height of a heap is defined to be the height of its root. The heap has minimum number of elements when height h contains only one element, and the heap has maximum number of elements when height contains $2^h$ elements.

So the minimum number of elements is $1 + 2^1 + 2^2 + \ldots + 2^{h - 1} + 1 = 2^h$.

The maximum number of elements below root is $1 + 2^1 + 2^2 + \ldots + 2^h = 2^{h + 1} - 1$.

6.1-2

In the previous question we have proved if a heap has height h, then the number of elements n satisfies $2^h \leq n \leq 2^{h + 1} - 1$. So $2^h \leq n < 2^{h + 1}$, thus $h \leq \lg{n} < h + 1$, so $h = \lfloor \lg{n} \rfloor$.

6.1-3

In a max-heap, for every node i other than the root, $A[PARENT(i)] \geq A[i]$. So the root of a subtree contains the value that is greater than its left and right children. Since the left and right children are also the root of their own subtree, their values are greater than their own children's values. Thus, the root of the subtree contains the largest value occurring anywhere in that subtree.

6.1-4

It cannot be a root of subtree, it must be a leaf.

6.1-5

If the array is in increasing order, then for any index $i \leq j$, we have $A[i] \leq A[j]$, thus for any root index i of a subtree in heap, the left child index is 2i, and the right child index is 2i + 1, it's obvious that i < 2i and i < 2i + 1, thus $A[i] \leq A[2i]$ and $A[i] \leq A[2i + 1]$, so it's a min-heap.

But if the array is in descending order, it's not a min-heap.

6.1-6

The subtree root index of 4 has right child with index 9, but A[4] < A[9]. So it's not a max-heap.

6.1-7

If a root of subtree has index i, then its left child index is 2i, and its right child index is 2i + 1. So it must satisfy $2i \leq n$, $i \leq \lfloor \frac{n}{2} \rfloor$. So the maximum index of subtree root is $\lfloor \frac{n}{2} \rfloor$, so the leaves are the nodes indexed by $\lfloor \frac{n}{2} \rfloor + 1, \lfloor \frac{n}{2} \rfloor + 2, \ldots, n$.