Editing Binary heap (section)

== Derivation of index equations ==
In an array-based heap, the children and parent of a node can be located via simple arithmetic on the node's index. This section derives the relevant equations for heaps with their root at index 0, with additional notes on heaps with their root at index 1.

To avoid confusion, we define the '''level''' of a node as its distance from the root, such that the root itself occupies level 0.

=== Child nodes ===

For a general node located at index {{mvar|i}} (beginning from 0), we will first derive the index of its right child, <math>\text{right} = 2i + 2</math>.

Let node {{mvar|i}} be located in level {{mvar|L}}, and note that any level {{mvar|l}} contains exactly <math>2^l</math> nodes. Furthermore, there are exactly <math>2^{l + 1} - 1</math> nodes contained in the layers up to and including layer {{mvar|l}} (think of binary arithmetic; 0111...111 = 1000...000 - 1). Because the root is stored at 0, the {{mvar|k}}th node will be stored at index <math>(k - 1)</math>. Putting these observations together yields the following expression for the '''index of the last node in layer {{mvar|l}}'''.

::<math>\text{last}(l) = (2^{l + 1} - 1) - 1 = 2^{l + 1} - 2</math>

Let there be {{mvar|j}} nodes after node {{mvar|i}} in layer L, such that

::<math>\begin{alignat}{2}
i = & \quad \text{last}(L) - j\\
  = & \quad (2^{L + 1} -2) - j\\
\end{alignat}
</math>

Each of these {{mvar|j}} nodes must have exactly 2 children, so there must be <math>2j</math> nodes separating {{mvar|i}}'s right child from the end of its layer (<math>L + 1</math>).

::<math>\begin{alignat}{2}
\text{right} = & \quad \text{last(L + 1)} -2j\\
             = & \quad (2^{L + 2} -2) -2j\\
             = & \quad 2(2^{L + 1} -2 -j) + 2\\
             = & \quad 2i + 2
\end{alignat}
</math>

Noting that the left child of any node is always 1 place before its right child, we get <math>\text{left} = 2i + 1</math>.

If the root is located at index 1 instead of 0, the last node in each level is instead at index <math>2^{l + 1} - 1</math>. Using this throughout yields <math>\text{left} = 2i</math> and <math>\text{right} = 2i + 1</math> for heaps with their root at 1.

=== 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>