1
$\begingroup$

I was reading heap data structures from various sources. They used to explain heap as stored in array. One source has array starting at index 0. Other has it starting at 1. They specify different equations for getting index of a parent for node at index 1.

Consider this heap:

enter image description here

1 based indices will be:

Elements: 78    56    32    45    8    23    19
Indices   1     2     3     4     5    6     7

I came across following two equations which correctly gave parent for 0-based indices, when I checked for indices 5 and 6, that is 23 and 19, both have parent 32 at index 2:

$\lfloor \frac{i-1}{2} \rfloor$ and $\lfloor \frac{i+1}{2}-1 \rfloor$

I came across following three equations which correctly gave parent for 1-based indices, when I checked for indices 5 and 6, that is 8 and 23. 8 have parent 56 at index 1 and 23 have parent 32 at index 3:

$\lceil \frac{i-1}{2} \rceil$,$\lceil \frac{i+1}{2} \rceil-1$ and $\lfloor \frac{i}{2} \rfloor$

How can I build mathematical intuition to just tell whether two equations involving ceil and floor functions are equal just at sight. Or given one equation with ceil and floor function, how can I derive all that are equivalent to it?

For example how can I quickly tell

  • $\lfloor \frac{i-1}{2} \rfloor$ is equivalent to $\lfloor \frac{i+1}{2}-1 \rfloor$ but not to $\lfloor \frac{i+1}{2} \rfloor-1$
  • $\lceil \frac{i-1}{2} \rceil$ is equivalent to $\lceil \frac{i+1}{2} \rceil-1$, but not to $\lceil \frac{i-1}{2} +1\rceil$

Is it possible to tell this only by trying out examples? Because I can guess at least 12 equations involving (add 1/substract 1/do nothng) in (numerator/inside/outside) of ceil/floor functions.

Pardon me for asking possibly primary maths question.

$\endgroup$
1
$\begingroup$

Regarding your two examples, note that $\frac{i+1}{2}-1 = \frac{i+1-2}{2} = \frac{i-1}{2}$, and $\frac{i-1}{2}+1 = \frac{i-1+2}{2} = \frac{i+1}{2}$. So it's not really about ceil and floor here, the expressions inside are just equal.

$\endgroup$
  • $\begingroup$ But then what about equivalences like: those in which ceil and floor $\lceil \frac{i-1}{2} \rceil = \lceil \frac{i+1}{2} \rceil-1$. Doesnt ceil function plays any role here? $\endgroup$ – anir Jan 14 at 19:31
  • 1
    $\begingroup$ Assume $i=2k+1, k \in \mathbb{N}$, then the right hand side evaluates to $k$ and the left hand side evaluates to $k+1-1$ so they are equal. Now let $i=2k, k \in \mathbb{N}$, then the right hand side evaluates to $k$ and the left hand side evaluates to $k+1-1$ once again. So they are equal. For a division by 3 you will have to check 3 cases ($3k, 3k+1, 3k+2$), for a division by $n$, you would have to check $n$ cases. $\endgroup$ – lightxbulb Jan 14 at 19:36
  • $\begingroup$ (1) Thats same as I checked with 5 and 6, right? You very well generalized it for arbitrary denominator. (2) And if I understood it all correct, we really have to manually check for such equivalences involving ceil and floor functions. Right? $\endgroup$ – anir Jan 14 at 19:45
  • 1
    $\begingroup$ Not exactly the same, but close enough. And yes, I do think you need to check the cases based on the denominator for expressions that are not equivalent inside the ceil. $\endgroup$ – lightxbulb Jan 14 at 19:52

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.