A binary heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices:
- The root element is
0
- Left child :
(2*i)+1
- Right child :
(2*i)+2
- Parent child :
(i-1)/2