CLRS Solutions 6.1 Heaps

6.1-1 

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

At least $2^h$ and at most $2^{h+1}-1$. Can be seen because a complete binary tree of depth $h-1$ has $\Sigma_{i=0}^{h-1}2^i = 2^h -1$ elements, and the number of elements in a heap of depth is $h$ between the number for a complete binary tree of depth $h-1$ exclusive and the number in a complete binary tree of depth $h$ inclusive.

6.1-2

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

Write $n = 2^m - 1 + k$ where $m$ is as large as possible. Then the heap consists of a complete binary tree of height $m-1$, along with $k$ additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these k leaves, which must have length $m$. It is clear from the way we defined $m$ that $m=\lfloor lgn \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.

If the largest element in the subtree were somewhere other than the root, it has a parent that is in the subtree. So, it is larger than it's parent, so, the heap property is violated at the parent of the maximum element in the subtree.

6.1-7

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

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

$LEFT(\lfloor n/2 \rfloor + 1) = 2(\lfloor n/2 \rfloor + 1)$

$>2 (\lfloor n/2 \rfloor + 1 - 1)$

$= 2(n/2)$

$= n$

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 numbers 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$.