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. We can see that for any given node, the enumeration for its child nodes and parent can easily be calculated using simple maths.

Enumeration of nodes in a complete binary tree

For any given node at the given `index`:

Parent = `(index - 1) / 2`

Left child = `(2 * index) + 1`

Right child = `(2 * index) + 2`