# Difficulty understanding the solution of heap problem in CLRS book?

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.

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.

• Can you elaborate more. I still can't get it. – toantruong Apr 17 at 16:39
• I think the number of leaves will be $(k-1)2^h$ plus some numbers. – toantruong Apr 17 at 16:40
• My supposed solution is this. Can you check if it is true. – toantruong Apr 17 at 17:21
• @toantruong It is $k[(2^h)+(2^{h-1}+1)]-1*2^h$ – Mr. Sigma. Apr 18 at 4:03
• 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. – toantruong Apr 18 at 4:36

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