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.

For any given node at the given `index` :

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