Course contentsShow
← Computer Science
Lesson 580 of 2,87214. Heaps and Priority QueuesFree lesson

Parent-Child Index Formulas

Master the formulas for finding parent (i/2) and children (2i, 2i+1) indices in the array representation.

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.