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`