text: # 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
explanation: The document contains a math question and a partial attempt at solving it. The question is about proving that the number of nodes of height \( h \) in a binary heap is not greater than \( \lceil \frac{n}{2^{h+1}} \rceil \). The user provides their thought process and some initial steps towards a solution but does not complete the proof. There are also comments from other users discussing the properties of binary heaps and the context of the problem.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document contains a math question and a partial attempt at solving it. The question is about proving that the number of nodes of height \( h \) in a binary heap is not greater than \( \lceil \frac{n}{2^{h+1}} \rceil \). The user provides their thought process and some initial steps towards a solution but does not complete the proof. There are also comments from other users discussing the properties of binary heaps and the context of the problem.
  
  Label: question-and-answer