# 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, 2016 at 0:12
• @LeeGao, it is book question, I suppose it is usual binary heap, as there was nothing about balancing in this chapter Nov 16, 2016 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). Nov 16, 2016 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, 2016 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, 2016 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.

Note that depth is the number of edges from the root & height is the number of edges from the highest level in a heap.

• consiser heap... n=4 when height is 0 ceil(n/2)=2 (upper bound is fine) when height is 1 ceil(n/4)=1 (here the upper bound is not correct) when height is 2 ceil(n/8)=1 (here it is correct) consider this heap... n=5 when height is 0 ceil(n/2)=3 (upper bound is fine) when height is 1 ceil(n/4)=2 (here the upper bound is correct) when height is 2 ceil(n/8)=1 (here it is correct) please explain me why is it so?? have I made any mistake in understanding the theorem statement?? Apr 3, 2020 at 6:02
• Could you please explain why is depth of tree $\lceil \lg n\rceil-1$ while I read and proved $\lfloor \lg n \rfloor$ ? Jul 9, 2020 at 15:53
• @SachinBahukhandi Ain't both expressions same? Jul 11, 2020 at 8:06
• Well how, I am confused on that. Please explain. Thank you. I know that $\lfloor x \rfloor \le x \le \lceil x \rceil$ Jul 11, 2020 at 15:48