Heap Representation in Arrays
Explore how heaps can be implemented using arrays by understanding the storage of parent and leaf nodes and the calculation of left and right child indices. This lesson helps you grasp the fundamental structure of heaps for better coding interview preparation in Java.
We'll cover the following...
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 ...