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

  • $\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 '16 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 Nov 16 '16 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 Nov 16 '16 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 '16 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 '16 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.


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.