6.1 Heaps

6.1-1

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

minimum numbers: $2^h$; maximun numbers: $2^{h+1}-1$

6.1-2

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

$h=m$ for $2^{m} \leq n \leq 2^{m+1}-1 \iff h=\lfloor \lg n \rfloor$

6.1-3

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

For each node with index $i$ in the subtree, $A[i]\leq A[parent(i)] \leq A[parent(parent(i))]\leq ... \leq A[root\text{(of the subtree)}.i]$

6.1-4

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

Since all elements are distinct, it is obviously that the smallest element must reside in leaves, otherwise its child has smaller value than it.

Then we need to consider whether if every leaf can be the smallest element? In a sense it is true.

6.1-5

At which levels in a max-heap might the $k$th largest element reside, for $2\leq k \leq \lfloor n/2 \rfloor$, assuming that all elements are distinct?

Let $f(k)$ be the levels in a max-heap might the $k$th largest element reside.

Since $A[i] \leq A[parent(i)]$, $f(k)\leq k$, and of course $f(k)\leq \lfloor \lg n \rfloor$

Since $2 \leq k$, $2\leq f(k)$

In conclusion, $2 \leq f(k) \leq \min(k,\lfloor \lg n \rfloor)$

6.1-6

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

Yes. For any node index i, LEFT(i) and RIGHT(i) are larger, and the element indexed by them are greater or equal to $A[i]$(in sorted array).

6.1-7

Is the array with values $<33,19,20,25,13,10,2,13,16,12>$ a max-heap?

No. the left child of the $A [ 2 ] (16) $ is $25$, which is larger than 19.

6.1-8

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

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

Since the nodes indexed by $\lfloor n/2 \rfloor$ has child while the nodes indexed by $\lfloor n/2 \rfloor + 1$ not, the leaves are the nodes indexed by $\lfloor n/2 \rfloor + 1,\lfloor n/2 \rfloor + 2,...,n$.