Difficulty understanding the solution of heap problem in CLRS book?

Question

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.

Answer 1

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$

Answer 2

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.