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$.
Comments
Post a Comment