Parent-Child Index Formulas
What you'll learn: How to navigate parent-child relationships in a heap using simple arithmetic on array indices.
Since we're representing a complete binary heap as an array (no pointers!), we need a way to "jump" between parents and children using just index math. The beauty of the complete binary tree structure is that these relationships follow predictable formulas.
The Core Formulas
When a node is stored at index i:
- Parent index:
i / 2(using integer division) - Left child index:
2 * i - Right child index:
2 * i + 1
These formulas assume 1-based indexing (array starts at index 1, not 0).
Why These Work
Think of the array as filling the tree level by level, left to right. Each parent "spawns" two children in consecutive positions. When you're at position i, your children naturally fall at positions that are roughly double your index—one at exactly 2i and the next right after at 2i + 1.
Going up the tree, you're essentially reversing this doubling, which means dividing by 2.
0-Based Indexing Variant
If your array uses 0-based indexing (more common in real code), the formulas adjust slightly:
- Parent:
(i - 1) / 2 - Left child:
2 * i + 1 - Right child:
2 * i + 2
The offset accounts for starting at index 0 instead of 1.
Example
In a 1-based array, if node 3 is a parent:
- Left child is at index
2 * 3 = 6 - Right child is at index
2 * 3 + 1 = 7 - Node 7's parent is at
7 / 2 = 3
Key Takeaway: Parent-child navigation in array-based heaps uses simple formulas—i/2 for parent, 2i and 2i+1 for children (1-based)—eliminating the need for pointer structures.