# Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

My thoughts process: let number of elements in heap be $$n$$, total height of binary heap be $$H$$, height of node be $$h$$, and let number of nodes with height $$h$$ be $$x$$.

Then number of nodes with height $$H-1 \le 2^1, H-2 \le 2^2, ... => x \le 2^{H-h} = 2^{\lfloor \lg n \rfloor - h} = \frac{2^{\lfloor \lg n \rfloor }}{2^h}$$

However, I don't see how this can be transformed to $$\lceil \frac{n}{2^{h+1}} \rceil$$, as $$n/2$$ is less than $$2^{\lfloor \lg n \rfloor }$$

• Is this a binary heap with just the usual heap invariant or does it also have some balance constraints that it has to satisfy as well? For example, I can create a degenerate heap that's just a list that nevertheless satisfies the heap invariant (namely, that the children must be smaller than the parent). – Lee Nov 16 '16 at 0:12
• @LeeGao, it is book question, I suppose it is usual binary heap, as there was nothing about balancing in this chapter – Joe Half Face Nov 16 '16 at 0:20
• @LeeGao According to wikipedia, a binary heap is defined to have the property of a complete binary tree (All levels except possible the lowest one are fully filled, and the lowest level is filled from left to right). – skankhunt42 Nov 16 '16 at 7:07
• I wasn't aware that this is the standard definition. I was taught that binary heaps should satisfy the shape property, but that it isn't always required. – Lee Nov 16 '16 at 8:04
• If it's from a book, can you give the citation to the book where it appears and the chapter & exercise number? There's a chance it might help others to look up the context there (e.g., how that book defines binary heap), if they have a copy too. – D.W. Nov 16 '16 at 16:30

$$n$$ element tree has depth $$\lceil{\log_2n}\rceil-1$$. If $$h$$ is the height of nodes in any $$n$$ element heap from leaves then the nodes are situated at the depth of $$\lceil{\log_2n}\rceil-1-h$$ from the root.
Now, at most $$2^{\lceil{\log_2n}\rceil-1-h} = \lceil{\frac{n}{2^{h+1}}}\rceil$$ nodes/leaves are possible with $$\lceil{\log_2n}\rceil-1-h$$ depth in a heap.