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