How Do Heap Indexes Work? Parent and Child Arithmetic

A binary heap is a complete tree kept in an array. Complete means every level is full except possibly the last, which fills from the left. That shape is why a child index is a formula.

How it works

Index 0 is the root. It has no parent. For a later index i:

• the parent is Math.floor((i - 1) / 2)
• the left child index is 2 * i + 1
• the right child index is 2 * i + 2

Those child indexes can sit past the end of a short array. The formula does not check the length. The heap operations do, when they decide whether a child exists.

A min-heap keeps each parent less than or equal to its children, so the smallest value sits at index 0. Inserting at the end and swapping upward, or moving the last value to the root and swapping downward, both follow these indexes. Each swap walks one level, and the height is about log n.

ThemeKiln

Terminal

Press Run to execute this example. Use console.log to print a value.

ResetRun

Expected output: { parent: null, left: 1, right: 2 }, then { parent: 1, left: 9, right: 10 }. Child indexes describe positions; callers must still compare them with the heap length.

Worked example

Index 4 is the right child of index 1 because Math.floor((4 - 1) / 2) = 1. Its own children would occupy indexes 9 and 10. In a heap of length 7 those children do not exist, even though the formulas still produce their positions.

Why it is correct

Level-order storage places the two children of index i immediately after all children of earlier indexes, at 2i + 1 and 2i + 2. For any non-root child c, both members of its sibling pair reduce to the same parent under Math.floor((c - 1) / 2). These formulas describe positions; existence still requires an array-length check.

Cost

Every formula uses a constant number of arithmetic operations, so parent and child calculations are O(1) time and O(1) space. Heap insertion or removal is O(log n) because it may repeat a parent-or-child step once per tree level.

In the course

Heaps introduce the formulas and then ask you to check the parent rule. The next lesson asks for the parent index and the two child indexes on their own, before any swaps. The kth-largest exercise is where the swaps earn their keep.

Common mistakes

Using 2 * i as the left child. That index is an even slot, not the left child of i. The left child is 2 * i + 1.

Returning the value at the child index when the question asked for the index.

Treating a missing child as a broken heap. A short last level is what "complete" allows. You only compare a child that exists.

When to use it

Use the formulas whenever you store a heap, or any complete binary tree, in an array and need the parent or a child without pointers.

When not to

Do not use heap indexes for a binary search tree that can be sparse. A missing left child in a BST is not "the next array slot". That tree wants real links.

Problem-solving checklist

Separate an index from the value stored there. Handle the root's missing parent explicitly. Before reading a child, compare its index with heap.length. Test the root, a left child, a right child, and a leaf on an incomplete last level.

Optional enrichment

Given a min-heap array, verify the parent rule for every existing child. Return the first violating pair of indexes, or null; do not attempt to repair the heap.