I am reading the solution of this problem in CLRS:

Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.

Solution: All the nodes of height $h$ partition the set of leaves into sets of size between $2^{h-1}$ and $2^h$, where all but one is size $2^h$. Just by putting all the children of each in their own part of the partition. Recal from 6.1-2 that the heap has height $\lfloor\lg(n)\rfloor$, so, by looking at the one element of this height (the root), we get that there are at most $2^{\lfloor\lg(n)\rfloor}$ leaves. Since each of the vertices of height $h$ partitions this into parts of size at least $2^{h-1}+1$, and all but one corresponds to a part of size $2^h$, we can let $k$ denote the quantity we wish to bound, so,

$$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$$ so $$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$$

But I don't understand how to come up with the fact that $(k-1)2^h + k(2^{h-1} + 1)$ is less than the number of leaves.


My solution to the question is this. Can you check if there is any flaw in this solution.

All but one of the node with height $h$ are full binary tree, so the number of leaves in these trees are $2^h$. The other one will have at least one leave. So the number of leaves is at least $(k-1)2^h + 1$ and it is bounded by $\frac{n}{2}$. So we have $(k-1)2^h + 1 \leqslant \frac{n}{2}$. From that, we can derive that $k \leqslant 1 + \frac{n}{2^{h+1}} - \frac{1}{2^h} \leqslant 1 + \frac{n}{2^{h+1}}$. So we have $k \leqslant \lceil \frac{n}{2^{h+1}} \rceil$


But I don't understand the how to come up with the fact that $(k−1)2^h+k(2^{h−1}+1)$ is less than the number of leaves.

It is quite straightforward from the very first statement of the solution which says there are all but one set of size $2^{h}$. Where $k$ is total number of sets of nodes at height $h$.

Therefore, total number of nodes at $h$ height is: $$\begin{align*} s &= (\text{total sets} \times \text{size of each sets})\\ &= k(2^{h}+2^{h-1}+1)-1 \cdot 2^{h}\\ &= (k−1)2^h+k(2^{h−1}+1) \end{align*}$$

Another way to solve this is here.

  • $\begingroup$ Can you elaborate more. I still can't get it. $\endgroup$ – toantruong Apr 17 '19 at 16:39
  • $\begingroup$ I think the number of leaves will be $(k-1)2^h$ plus some numbers. $\endgroup$ – toantruong Apr 17 '19 at 16:40
  • $\begingroup$ My supposed solution is this. Can you check if it is true. $\endgroup$ – toantruong Apr 17 '19 at 17:21
  • $\begingroup$ @toantruong It is $k[(2^h)+(2^{h-1}+1)]-1*2^h$ $\endgroup$ – Mr. Sigma. Apr 18 '19 at 4:03
  • $\begingroup$ I still don't get this formula. If we have a full binary tree with height $2$, and we compute the number of nodes with height $1$, so in this case $k = 2$. If I apply your formula, we will have $k[2^h + (2^{h-1}+1)] - 2^h = 6$, but in this case, the heap has only $4$ leaves. $\endgroup$ – toantruong Apr 18 '19 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.