Heap Representation in Arrays

The lesson elaborates how to Use Arrays for the Implementation of Heaps.

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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.