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

$\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
    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$ 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$ 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
    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.
    Nov 16, 2016 at 16:30

1 Answer 1

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.

$\endgroup$
4
  • $\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$ 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$ Jul 9, 2020 at 15:53
  • $\begingroup$ @SachinBahukhandi Ain't both expressions same? $\endgroup$
    – Mr. Sigma.
    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$ Jul 11, 2020 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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