1
$\begingroup$

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 }$

Improve this question
$\endgroup$
8
  • $\begingroup$ 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). $\endgroup$
    – Lee
    Commented Nov 16, 2016 at 0:12
  • $\begingroup$ @LeeGao, it is book question, I suppose it is usual binary heap, as there was nothing about balancing in this chapter $\endgroup$
    – Joe Half Face
    Commented Nov 16, 2016 at 0:20
  • $\begingroup$ @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). $\endgroup$
    – skankhunt42
    Commented Nov 16, 2016 at 7:07
  • $\begingroup$ 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. $\endgroup$
    – Lee
    Commented Nov 16, 2016 at 8:04
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Nov 16, 2016 at 16:30

1 Answer 1

Reset to default
1
$\begingroup$

$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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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?? $\endgroup$
    – Abhishek Ghosh
    Commented Apr 3, 2020 at 6:02
  • $\begingroup$ Could you please explain why is depth of tree $\lceil \lg n\rceil-1$ while I read and proved $\lfloor \lg n \rfloor$ ? $\endgroup$
    – Sachin Bahukhandi
    Commented Jul 9, 2020 at 15:53
  • $\begingroup$ @SachinBahukhandi Ain't both expressions same? $\endgroup$
    – Mr. Sigma.
    Commented Jul 11, 2020 at 8:06
  • $\begingroup$ Well how, I am confused on that. Please explain. Thank you. I know that $\lfloor x \rfloor \le x \le \lceil x \rceil $ $\endgroup$
    – Sachin Bahukhandi
    Commented Jul 11, 2020 at 15:48
  • $\begingroup$ @Mr.Sigma. Bit late on this, but when plotted in Desmos, your final simplification to get the result doesn't seem to be true? $\endgroup$
    – Blahblahblacksheep
    Commented Apr 19 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.