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.

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 parents would be different (how?).