An array representation stores a complete, left-adjusted tree compactly in index order. For a heap, this removes child and parent pointers while preserving the tree structure through arithmetic on indices. section 2.5.3
With zero-based indexing, navigate the binary heap using these relationships:
- The children of the node at index i occupy indices 2*i + 1 and 2*(i + 1). section 2.5.3
- The parent of node i is at index (i - 1) / 2, except for the root. section 2.5.3
- The tree maps into the array from top to bottom and left to right, so a heap with N elements needs an array of N elements. section 2.5.3
Navigating a heap
For a node at index 1, the children are at indices 3 and 4, and the parent is at index 0. A node at index 5 has parent index 2 and potential children at indices 11 and 12. section 2.5.3
This representation is efficient when operations preserve completeness: heaps add and remove at the array tail, then bubble one element up or push it down. It becomes inflexible when arbitrary elements must move; inserting into the middle of an ordered array can require linear-time shifting. Rotations make arrays unsuitable for treaps and binary search trees. section 3.3.2
