Heap Representation in Arrays

Heaps can be implemented using Arrays. The contents of a heap with n nodes are stored in such a way that all the parent nodes occur in the first half of array (n/2), while the leaves are present at the last n/2 positions. So the last parent will be at the n/2th position.

The node at the kth position will have its children placed as follows:

• The Left child at 2k+1
• The Right child at 2k+2.

See the figure below to see how nodes are mapped on the array:

In the figure above, you can see that all of the parent nodes are present in the first half of the array, with the last parent at the n/2th position (i.e. 4th index), whereas the children nodes ...