0
$\begingroup$

I recently came across the question:

Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap.

I looked for some solutions and found this one: Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

But I got confused with the answer which used the expression: $$\lceil{\log_2n}\rceil-1$$ as the height of the tree.

But, I am confused because I have earlier proved that the height of the tree is:

$$\lfloor \lg n \rfloor$$

Even if I consider both are the same it could only be true if $\lg n$ returns a decimal value instead of an integer.

For example, consider an example of taking $n=4$ the example would fail as:

$$\lfloor \lg n \rfloor \le \lg n \le \lceil \lg n \rceil$$

Please help.

Thank you.

$\endgroup$
7
  • $\begingroup$ Might be an off-by-one issue, that is, one of the $n$ should be $n+1$ or $n-1$. $\endgroup$ Jul 14 '20 at 18:40
  • $\begingroup$ Sorry, I did not get you. Could you please explain? $\endgroup$ Jul 14 '20 at 18:44
  • 1
    $\begingroup$ For example, I believe that $\lfloor \log_2 n \rfloor = \lceil \log_2 (n+1) \rceil - 1$ (unless $n$ is very small). $\endgroup$ Jul 14 '20 at 20:06
  • $\begingroup$ Yeah but doesn't this mean that the answer : cs.stackexchange.com/a/107090/85651 is wrong? $\endgroup$ Jul 14 '20 at 20:09
  • 1
    $\begingroup$ I wouldn't worry so much about such small inaccuracies. $\endgroup$ Jul 14 '20 at 20:11
1
$\begingroup$

The expression $\lceil \log_2 n \rceil - 1$ for the height of a $n$-element heap is wrong. For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc...

In general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log_2 2^i \rceil - 1 = i-1$.

The equality $\lceil \log_2n \rceil -1=\lfloor \log_2 n\rfloor$ is also wrong, as it can be seen by picking $n=2^i$ for any $i \in \mathbb{N}^+$.

$\endgroup$
2

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.