# 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
Commented 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 Commented 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). Commented 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
Commented 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.
Commented 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.
• Could you please explain why is depth of tree $\lceil \lg n\rceil-1$ while I read and proved $\lfloor \lg n \rfloor$ ? Commented Jul 9, 2020 at 15:53
• Well how, I am confused on that. Please explain. Thank you. I know that $\lfloor x \rfloor \le x \le \lceil x \rceil$ Commented Jul 11, 2020 at 15:48
The text passage contains a mathematical question about proving a property of binary heaps, specifically the number of nodes of height \( h \) in a binary heap. The passage also includes a discussion and an attempted proof, but it does not provide a complete answer to the question.
single_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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
Commented 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 Commented 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). Commented 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
Commented 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.
Commented 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.
• Could you please explain why is depth of tree $\lceil \lg n\rceil-1$ while I read and proved $\lfloor \lg n \rfloor$ ? Commented Jul 9, 2020 at 15:53
• Well how, I am confused on that. Please explain. Thank you. I know that $\lfloor x \rfloor \le x \le \lceil x \rceil$ Commented Jul 11, 2020 at 15:48
user
The text passage contains a mathematical question about proving a property of binary heaps, specifically the number of nodes of height \( h \) in a binary heap. The passage also includes a discussion and an attempted proof, but it does not provide a complete answer to the question.

TYPE: SINGLE_QUESTION