Ranked Array Representation
- Explain how a binary heap can be represented using a (ranked) array.
A complete binary tree can be uniquely represented by storing its level order traversal in an array.
![](/img/20/rank.png)
The root is the second item in the array. We skip the index zero cell of the array for the convenience of implementation. Consider $k^{\text(th)}$ element of the array,
- its left child is located at
2 * k
index - its right child is located at
2 * k + 1
index - its parent is located at
k / 2
index
Exercise Do we have to skip index zero?
Solution
No! We could start at index zero. However, the formulas for getting children and parent would be different (how?).