Editing Binary heap (section)

=== Parent node ===

Every non-root node is either the left or right child of its parent, so one of the following must hold:

* <math>i = 2 \times (\text{parent}) + 1</math>
* <math>i = 2 \times (\text{parent}) + 2</math>

Hence,
::<math>\text{parent} = \frac{i - 1}{2} \;\textrm{ or }\; \frac{i - 2}{2}</math>

Now consider the expression <math>\left\lfloor \dfrac{i - 1}{2} \right\rfloor</math>.

If node <math>i</math> is a left child, this gives the result immediately, however, it also gives the correct result if node <math>i</math> is a right child. In this case, <math>(i - 2)</math> must be even, and hence <math>(i - 1)</math> must be odd.

::<math>\begin{alignat}{2}
\left\lfloor \dfrac{i - 1}{2} \right\rfloor = & \quad \left\lfloor \dfrac{i - 2}{2} + \dfrac{1}{2} \right\rfloor\\
= & \quad \frac{i - 2}{2}\\
= & \quad \text{parent}
\end{alignat}
</math>

Therefore, irrespective of whether a node is a left or right child, its parent can be found by the expression:

::<math>\text{parent} = \left\lfloor \dfrac{i - 1}{2} \right\rfloor</math>