Editing Binary heap (section)

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