Structure of array based heap

Now that we know that a heap is a complete binary tree, it is easy to understand how it is implemented using an array. We can easily identify a pattern if we enumerate the nodes of a complete binary tree starting with 0 at the root (going level by level, left to right). We can see that for any given node, the enumeration for its child nodes and parent can easily be calculated using simple maths (using integer division, so any fractional part is dropped).

For any given node at the given `index`:

• Parent = `(index - 1) / 2`
• Left child = `(2 * index) + 1`
• Right child = `(2 * index) + 2`