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: