Data Structures & AlgorithmsHeaps & Priority Queues

Array-Based Heap Implementation

LevelIntermediate

Duration60 mins

TopicHeaps & Priority Queues

2 / 4

Parent and Child Index Formulas

The Arithmetic of Tree Navigation

In a pointer-based tree, finding a node's parent or children is trivial: just follow the pointer. In an array-based heap, we have no pointers—only indices. Yet we need to navigate the implicit tree structure fluently: moving up to parents during bubble-up operations, moving down to children during bubble-down operations.

The solution is index arithmetic. Simple mathematical formulas relate any node's index to its parent and children. These formulas are the operational heart of array-based heaps. Every insert, every extract, every heap operation relies on these relationships.

While the formulas themselves are simple, understanding their derivation builds intuition for why they work. And choosing between 0-based and 1-based indexing—a seemingly minor decision—has implications for formula elegance and implementation clarity.

What You Will Learn

By the end of this page, you will: (1) Derive the parent-child index formulas from first principles, (2) Master both 0-based and 1-based conventions, (3) Understand why 1-based indexing yields cleaner formulas, (4) Know how to handle boundary conditions (root has no parent, leaves have no children), and (5) Implement robust helper functions for tree navigation.

The Core Formulas

Let's state the formulas upfront, then derive and explore them in depth.

For 1-based indexing (root at index 1):

Parent of node i: ⌊i/2⌋
Left child of node i: 2i
Right child of node i: 2i + 1

For 0-based indexing (root at index 0):

Parent of node i: ⌊(i-1)/2⌋
Left child of node i: 2i + 1
Right child of node i: 2i + 2

Parent-Child Formulas: 0-Based vs 1-Based
Relationship	1-Based (root = 1)	0-Based (root = 0)
Parent of i	⌊i/2⌋	⌊(i-1)/2⌋
Left child of i	2i	2i + 1
Right child of i	2i + 1	2i + 2
Is left child?	i is even	i is odd
Is right child?	i is odd (and i > 1)	i is even (and i > 0)

Observe that 1-based indexing produces cleaner, more symmetric formulas. The parent is simply half the index; the left child is double the index. This elegance isn't coincidental—it reflects the binary structure of the tree mapping naturally to binary arithmetic.

However, most programming languages use 0-based array indexing. Using 1-based indexing requires either wasting index 0 or adding offset adjustments throughout the code. We'll explore both approaches.

Memory Aid

For 1-based: Parent = half, Children = double. For 0-based: Think of it as 1-based formulas with offset corrections. Parent subtracts 1 before halving; children add 1 or 2 after doubling.

Deriving the 1-Based Formulas

The 1-based formulas aren't arbitrary—they emerge naturally from the level-order numbering of a complete binary tree. Let's derive them from first principles.

Setup:

With 1-based indexing:

Level 0: index 1 (just the root)
Level 1: indices 2, 3
Level 2: indices 4, 5, 6, 7
Level 3: indices 8–15
Level k: indices 2^k to 2^(k+1) - 1

1
2
3
4
5
6
7
              [1]                    Level 0: 1 node
             /   \
          [2]     [3]                 Level 1: 2 nodes
         /  \    /   \
       [4] [5] [6]   [7]              Level 2: 4 nodes
      /  \  / \  / \   / \
    [8][9][10][11][12][13][14][15]    Level 3: 8 nodes

Deriving the child formulas:

Consider node at index i on level k. Its position within level k is (i - 2^k).

The left child is at level k+1, and its position within that level is 2(i - 2^k) (because each node in level k spawns two nodes in level k+1, maintaining left-to-right order).

The index of the left child:

First index of level k+1: 2^(k+1)
Position within level k+1: 2(i - 2^k)
Left child index: 2^(k+1) + 2(i - 2^k) = 2^(k+1) + 2i - 2^(k+1) = 2i

The right child is simply one position after the left child: 2i + 1.

The Beauty of Binary

The formula 'left child = 2i' corresponds to left-shifting in binary: 2i = i << 1. Similarly, 'right child = 2i+1' is a left-shift followed by setting the lowest bit: (i << 1) | 1. The binary representation of a node's index encodes the path from root to that node!

Deriving the parent formula:

The parent formula is the inverse of the child formulas. If node p has left child 2p and right child 2p+1, then:

The parent of an even index i is i/2
The parent of an odd index i is (i-1)/2

Both cases are captured by integer division: ⌊i/2⌋.

In programming terms, integer division of i by 2 automatically floors the result, handling both even and odd cases correctly.

Verification by example:

For index 11:

Parent: ⌊11/2⌋ = 5 ✓ (node 5 has children 10 and 11)
Left child: 2×11 = 22
Right child: 2×11 + 1 = 23

For index 6:

Parent: ⌊6/2⌋ = 3 ✓ (node 3 has children 6 and 7)
Left child: 2×6 = 12
Right child: 2×6 + 1 = 13

Deriving the 0-Based Formulas

The 0-based formulas are derived by offsetting the 1-based formulas. The relationship is:

If 1-based index is j, then 0-based index is i = j - 1, so j = i + 1

Deriving children:

In 1-based terms, left child of node j is 2j. Converting:

0-based parent index: i = j - 1, so j = i + 1
1-based left child: 2j = 2(i + 1) = 2i + 2
0-based left child: (2i + 2) - 1 = 2i + 1

Similarly, right child:

1-based right child: 2j + 1 = 2(i + 1) + 1 = 2i + 3
0-based right child: (2i + 3) - 1 = 2i + 2

1
2
3
4
5
6
7
              [0]                    Level 0: 1 node
             /   \
          [1]     [2]                 Level 1: 2 nodes
         /  \    /   \
       [3] [4] [5]   [6]              Level 2: 4 nodes
      /  \  / \  / \   / \
    [7][8][9][10][11][12][13][14]     Level 3: 8 nodes

Deriving parent:

In 1-based terms, parent of node j is ⌊j/2⌋. Converting:

0-based child index: i = j - 1, so j = i + 1
1-based parent: ⌊(i + 1)/2⌋
0-based parent: ⌊(i + 1)/2⌋ - 1

Simplifying: ⌊(i + 1)/2⌋ - 1 = ⌊(i + 1 - 2)/2⌋ = ⌊(i - 1)/2⌋

Verification by example:

For index 10 (0-based):

Parent: ⌊(10-1)/2⌋ = ⌊9/2⌋ = 4 ✓ (node 4 has children 9 and 10)
Left child: 2×10 + 1 = 21
Right child: 2×10 + 2 = 22

For index 5 (0-based):

Parent: ⌊(5-1)/2⌋ = ⌊4/2⌋ = 2 ✓ (node 2 has children 5 and 6)
Left child: 2×5 + 1 = 11
Right child: 2×5 + 2 = 12

Watch the Offset

The most common bug in 0-based heap implementations is forgetting the offset. Using '2i' instead of '2i+1' for the left child, or 'i/2' instead of '(i-1)/2' for the parent, will produce incorrect results. Always verify your formulas against a diagram.

Implementation Patterns

Let's translate these formulas into production-quality code with proper handling of edge cases.

Pattern 1: 0-based indexing (standard approach)

This is the most common pattern since most languages use 0-based arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Heap<T> {
    private data: T[] = [];
    
    // Parent index (returns -1 for root to indicate no parent)
    private parent(i: number): number {
        if (i === 0) return -1; // Root has no parent
        return Math.floor((i - 1) / 2);
    }
    
    // Left child index (may be beyond array bounds)
    private leftChild(i: number): number {
        return 2 * i + 1;
    }
    
    // Right child index (may be beyond array bounds)
    private rightChild(i: number): number {
        return 2 * i + 2;
    }
    
    // Check if index has a left child
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) < this.data.length;
    }
    
    // Check if index has a right child
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) < this.data.length;
    }
    
    // Check if index is a leaf node
    private isLeaf(i: number): boolean {
        return !this.hasLeftChild(i);
    }
}

Pattern 2: 1-based indexing with padding

Some implementations prefer the cleaner 1-based formulas by wasting index 0:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Heap1Based<T> {
    private data: (T | null)[] = [null]; // Index 0 is unused padding
    
    // Actual heap size (excluding padding)
    get size(): number {
        return this.data.length - 1;
    }
    
    // Parent index (returns 0 for root, which is invalid)
    private parent(i: number): number {
        return Math.floor(i / 2);
    }
    
    // Left child index
    private leftChild(i: number): number {
        return 2 * i;
    }
    
    // Right child index
    private rightChild(i: number): number {
        return 2 * i + 1;
    }
    
    // Check if index has a left child
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) <= this.size;
    }
    
    // Check if index has a right child
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) <= this.size;
    }
    
    // Access element at index (1-based)
    private get(i: number): T {
        return this.data[i] as T;
    }
}

Choosing Your Convention

For most practical purposes, 0-based indexing is preferred—it aligns with language conventions and doesn't waste space. However, 1-based indexing can be valuable for teaching, mathematical proofs, or when translating algorithms from textbooks that use 1-based notation.

Handling Boundary Conditions

The formulas compute indices mathematically, but not every computed index is valid. Several boundary conditions must be handled:

1. Root has no parent

The root (index 0 in 0-based, index 1 in 1-based) has no parent. Applying the parent formula returns an invalid result:

0-based: parent(0) = ⌊(0-1)/2⌋ = ⌊-1/2⌋ = -1 (negative, clearly invalid)
1-based: parent(1) = ⌊1/2⌋ = 0 (which is the unused padding slot)

Always check before accessing the parent.

2. Leaves have no children

Leaf nodes have no children. The child formulas produce indices beyond the array bounds:

For a heap of size n, valid indices are 0 to n-1 (0-based) or 1 to n (1-based)
If leftChild(i) >= n, the node is a leaf
If leftChild(i) < n but rightChild(i) >= n, the node has only a left child

This last case is important: in a complete binary tree, the last internal node may have only a left child (the rightmost node on the second-to-last level).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class SafeHeap<T> {
    private data: T[] = [];
    
    // Safe parent access - returns undefined if no parent
    private getParentIndex(i: number): number | undefined {
        if (i <= 0) return undefined;
        return Math.floor((i - 1) / 2);
    }
    
    // Safe child access - returns undefined if no such child
    private getLeftChildIndex(i: number): number | undefined {
        const left = 2 * i + 1;
        return left < this.data.length ? left : undefined;
    }
    
    private getRightChildIndex(i: number): number | undefined {
        const right = 2 * i + 2;
        return right < this.data.length ? right : undefined;
    }
    
    // Get indices of all existing children (0, 1, or 2)
    private getChildIndices(i: number): number[] {
        const children: number[] = [];
        const left = this.getLeftChildIndex(i);
        const right = this.getRightChildIndex(i);
        if (left !== undefined) children.push(left);
        if (right !== undefined) children.push(right);
        return children;
    }
    
    // Find index of last non-leaf node
    // Useful for building heaps bottom-up
    private lastInternalNode(): number {
        return Math.floor(this.data.length / 2) - 1;
    }
    
    // Count of leaf nodes
    private leafCount(): number {
        return Math.ceil(this.data.length / 2);
    }
}

Leaf Node Count

In a complete binary tree with n nodes, exactly ⌈n/2⌉ are leaves and ⌊n/2⌋ are internal nodes. This is useful for algorithms like heapify that only need to process internal nodes.

3. Empty heap

An empty heap (n = 0) has no valid indices. All operations should check for this condition before accessing any index.

4. Single-element heap

With only the root (n = 1), there is no parent and no children. The root is simultaneously the minimum/maximum and a leaf.

Bit Manipulation Optimizations

The heap navigation formulas involve multiplication by 2, division by 2, and addition of small constants. These operations map directly to efficient bit operations:

Multiplication by 2: Left shift

2 * i = i << 1

Division by 2 (integer): Right shift

i / 2 = i >> 1 (for non-negative i)

Addition of 1: OR with 1

2i + 1 = (i << 1) | 1 (sets the lowest bit)

These aren't merely micro-optimizations—they reveal the underlying binary structure of heap indexing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 1-based indexing with bit operations
class BitHeap<T> {
    private data: T[] = [];
    
    // Parent: right shift by 1
    private parent(i: number): number {
        return i >> 1;
    }
    
    // Left child: left shift by 1
    private leftChild(i: number): number {
        return i << 1;
    }
    
    // Right child: left shift by 1, then set lowest bit
    private rightChild(i: number): number {
        return (i << 1) | 1;
    }
    
    // Check if node is a left child
    private isLeftChild(i: number): boolean {
        return (i & 1) === 0; // Even numbers are left children
    }
    
    // Check if node is a right child
    private isRightChild(i: number): boolean {
        return (i & 1) === 1 && i > 1; // Odd numbers (except 1) are right children
    }
    
    // Get sibling index
    private sibling(i: number): number {
        return i ^ 1; // XOR with 1 flips between left and right child
    }
}
 
// 0-based indexing equivalents
class BitHeap0Based<T> {
    private data: T[] = [];
    
    // Parent: (i-1) >> 1
    private parent(i: number): number {
        return (i - 1) >> 1;
    }
    
    // Left child: (i << 1) + 1
    private leftChild(i: number): number {
        return (i << 1) + 1;
    }
    
    // Right child: (i << 1) + 2
    private rightChild(i: number): number {
        return (i << 1) + 2;
    }
}

The XOR sibling trick:

For 1-based indexing, the sibling of node i is i XOR 1:

If i is even (left child), i XOR 1 = i + 1 (right sibling)
If i is odd (right child), i XOR 1 = i - 1 (left sibling)

This elegant property arises because left and right children are consecutive integers.

Modern Compilers Are Smart

Modern optimizing compilers typically convert 'i * 2' to 'i << 1' and 'i / 2' to 'i >> 1' automatically. Write whichever is more readable for your team. The bit operations are shown here for conceptual understanding, not because you must use them for performance.

Path from Root to Node

A powerful application of the index formulas is computing the path from the root to any node, or vice versa. This is useful for:

Debugging: Tracing how we reached a particular node
Understanding tree structure: Seeing the left/right decisions at each level
Advanced algorithms: Some heap variants need explicit path information

Path computation via binary representation (1-based):

For 1-based indexing, the binary representation of a node's index encodes its path from the root. Excluding the leading 1-bit:

0 means "go left"
1 means "go right"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Get path from root to node at index i (1-based)
function pathToNode(index: number): ('L' | 'R')[] {
    if (index <= 0) throw new Error('Invalid index');
    if (index === 1) return []; // Root has empty path
    
    const path: ('L' | 'R')[] = [];
    
    // Find the position of the highest set bit
    let temp = index;
    let bits: number[] = [];
    while (temp > 0) {
        bits.push(temp & 1);
        temp >>= 1;
    }
    bits.reverse();
    
    // Skip the leading 1, interpret remaining bits
    for (let i = 1; i < bits.length; i++) {
        path.push(bits[i] === 0 ? 'L' : 'R');
    }
    
    return path;
}
 
// Alternative: iterative parent traversal
function pathToNodeIterative(index: number): ('L' | 'R')[] {
    if (index <= 1) return [];
    
    const path: ('L' | 'R')[] = [];
    let current = index;
    
    while (current > 1) {
        const parent = current >> 1;
        if (current === parent * 2) {
            path.push('L');
        } else {
            path.push('R');
        }
        current = parent;
    }
    
    return path.reverse(); // Reverse to get root-to-node order
}
 
// Example usage:
// pathToNode(11) returns ['L', 'R', 'R']
// Binary of 11 is 1011: skip leading 1 -> 011 -> L, R, R

Index to Path Examples (1-Based)
Index	Binary	Path (excluding leading 1)
1	1	[] (root)
2	10	[L]
3	11	[R]
4	100	[L, L]
5	101	[L, R]
6	110	[R, L]
7	111	[R, R]
10	1010	[L, R, L]
13	1101	[R, L, R]

Depth Equals Bit Count Minus One

The depth (level) of a node equals the number of bits in its index minus 1. For index 13 (binary 1101, 4 bits), depth = 3. This is another way to see why height is O(log n)—the number of bits needed to represent n is ⌈log₂(n+1)⌉.

Comprehensive Formula Verification

To cement understanding, let's verify the formulas exhaustively for a small heap. This kind of manual verification is essential when first learning these relationships.

1
2
3
4
5
6
7
                    [0]
                  /      \
               [1]        [2]
              /   \      /    \
           [3]    [4]  [5]    [6]
          / \    / \   / \   / \
        [7][8] [9][10][11][12][13][14]

0-Based Index Relationships (Verified)
Node	Parent ⌊(i-1)/2⌋	Left 2i+1	Right 2i+2	Level ⌊log₂(i+1)⌋
0	— (root)	1	2	0
1	0 ✓	3	4	1
2	0 ✓	5	6	1
3	1 ✓	7	8	2
4	1 ✓	9	10	2
5	2 ✓	11	12	2
6	2 ✓	13	14	2
7	3 ✓	15 (OOB)	16 (OOB)	3
8	3 ✓	17 (OOB)	18 (OOB)	3
9	4 ✓	19 (OOB)	20 (OOB)	3
10	4 ✓	21 (OOB)	22 (OOB)	3
11	5 ✓	23 (OOB)	24 (OOB)	3
12	5 ✓	25 (OOB)	26 (OOB)	3
13	6 ✓	27 (OOB)	28 (OOB)	3
14	6 ✓	29 (OOB)	30 (OOB)	3

Observations from the table:

Every non-root node's parent formula produces the correct index
Nodes 7-14 (leaves) have children beyond the heap bounds (OOB = Out Of Bounds)
All nodes on the same level have consecutive indices
Parent indices are exactly half of child indices (accounting for the 0-based offset)
Siblings are always consecutive: (3,4), (5,6), (7,8), etc.

Build Your Own Table

Drawing out a small heap and computing all relationships by hand is one of the best ways to internalize these formulas. Do this once, and the formulas will feel natural rather than memorized.

Common Implementation Mistakes

Even simple formulas can harbor subtle bugs. Here are the most common mistakes when implementing heap navigation:

Common Mistakes to Avoid

•Mixing indexing conventions — Using 1-based parent formula with 0-based array indexing, or vice versa. Pick one and be consistent.
•Forgetting bounds checks — Accessing leftChild(i) without verifying it's within array bounds. Always check before dereferencing.
•Integer division confusion — In some languages, division operator behavior differs for negative numbers. Ensure you understand how your language handles '(-1)/2'.
•Off-by-one in heap size — Using 'heap.length' when you should use 'heap.length - 1', or vice versa. Document what 'size' means in your implementation.
•Treating root specially but incorrectly — The root (index 0 or 1) is special: it has no parent. But it's not special in other ways—don't add unnecessary special cases.
•Swapping formulas for parent/child — The child formula is NOT '2i - 1' for 0-based. It's '2i + 1'. Getting these backwards leads to incorrect heap structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class DefensiveHeap<T> {
    private data: T[] = [];
    
    private assertValidIndex(i: number, context: string): void {
        if (i < 0 || i >= this.data.length) {
            throw new Error(
                `Invalid heap index ${i} (size: ${this.data.length}) in ${context}`
            );
        }
    }
    
    private parentIndex(i: number): number {
        this.assertValidIndex(i, 'parentIndex');
        if (i === 0) {
            throw new Error('Root node has no parent');
        }
        return Math.floor((i - 1) / 2);
    }
    
    private leftChildIndex(i: number): number | undefined {
        this.assertValidIndex(i, 'leftChildIndex');
        const left = 2 * i + 1;
        return left < this.data.length ? left : undefined;
    }
    
    private rightChildIndex(i: number): number | undefined {
        this.assertValidIndex(i, 'rightChildIndex');
        const right = 2 * i + 2;
        return right < this.data.length ? right : undefined;
    }
    
    // Safe access with explicit undefined handling
    private getLeftChild(i: number): T | undefined {
        const idx = this.leftChildIndex(i);
        return idx !== undefined ? this.data[idx] : undefined;
    }
}

Defensive vs Performance

In production hot paths, you might remove these checks for performance. But during development and testing, defensive checks catch bugs immediately. Consider using assertions that can be stripped in production builds.

Summary: Navigating the Implicit Tree

The parent and child index formulas are the operational core of array-based heaps. Without them, we couldn't navigate the implicit tree structure. With them, traversal becomes simple arithmetic—no pointers, no chasing references, just numbers.

Let's consolidate the key takeaways:

Key Takeaways

•1-based formulas are elegant: Parent = i/2, Left = 2i, Right = 2i+1. The binary structure of the tree maps to binary arithmetic.
•0-based formulas require offsets: Parent = (i-1)/2, Left = 2i+1, Right = 2i+2. More complex but aligns with standard array indexing.
•Boundary conditions are critical: Root has no parent, leaves have no children. Always check bounds before accessing.
•Binary representation encodes paths: For 1-based indexing, the bits of an index (after the leading 1) specify the path from root.
•Bit operations are equivalent: Multiplication/division by 2 are left/right shifts. This isn't just optimization—it reveals structure.
•Consistency is paramount: Pick one indexing convention and use it everywhere. Mixing conventions is a recipe for bugs.

What's next:

With navigation formulas in hand, we can appreciate the full elegance of array-based heaps. The next page explores why no pointers are needed—not just mechanically (we've seen the formulas), but philosophically. What makes complete binary trees special enough that pointers become redundant? Understanding this deepens appreciation for the heap data structure's design.

Page Complete

You now possess the technical machinery to navigate array-based heaps: computing parents, children, levels, and paths through simple index arithmetic. These formulas will appear in every heap operation you ever write. Master them, and heap implementation becomes straightforward.

2 / 4

Loading learning content...

Data Structures & AlgorithmsHeaps & Priority Queues

Array-Based Heap Implementation

LevelIntermediate

Duration60 mins

TopicHeaps & Priority Queues

2 / 4

Parent and Child Index Formulas

The Arithmetic of Tree Navigation

What You Will Learn

The Core Formulas

Let's state the formulas upfront, then derive and explore them in depth.

For 1-based indexing (root at index 1):

Parent of node i: ⌊i/2⌋
Left child of node i: 2i
Right child of node i: 2i + 1

For 0-based indexing (root at index 0):

Parent of node i: ⌊(i-1)/2⌋
Left child of node i: 2i + 1
Right child of node i: 2i + 2

Parent-Child Formulas: 0-Based vs 1-Based
Relationship	1-Based (root = 1)	0-Based (root = 0)
Parent of i	⌊i/2⌋	⌊(i-1)/2⌋
Left child of i	2i	2i + 1
Right child of i	2i + 1	2i + 2
Is left child?	i is even	i is odd
Is right child?	i is odd (and i > 1)	i is even (and i > 0)

However, most programming languages use 0-based array indexing. Using 1-based indexing requires either wasting index 0 or adding offset adjustments throughout the code. We'll explore both approaches.

Memory Aid

For 1-based: Parent = half, Children = double. For 0-based: Think of it as 1-based formulas with offset corrections. Parent subtracts 1 before halving; children add 1 or 2 after doubling.

Deriving the 1-Based Formulas

The 1-based formulas aren't arbitrary—they emerge naturally from the level-order numbering of a complete binary tree. Let's derive them from first principles.

Setup:

With 1-based indexing:

Level 0: index 1 (just the root)
Level 1: indices 2, 3
Level 2: indices 4, 5, 6, 7
Level 3: indices 8–15
Level k: indices 2^k to 2^(k+1) - 1

1
2
3
4
5
6
7
              [1]                    Level 0: 1 node
             /   \
          [2]     [3]                 Level 1: 2 nodes
         /  \    /   \
       [4] [5] [6]   [7]              Level 2: 4 nodes
      /  \  / \  / \   / \
    [8][9][10][11][12][13][14][15]    Level 3: 8 nodes

Deriving the child formulas:

Consider node at index i on level k. Its position within level k is (i - 2^k).

The left child is at level k+1, and its position within that level is 2(i - 2^k) (because each node in level k spawns two nodes in level k+1, maintaining left-to-right order).

The index of the left child:

First index of level k+1: 2^(k+1)
Position within level k+1: 2(i - 2^k)
Left child index: 2^(k+1) + 2(i - 2^k) = 2^(k+1) + 2i - 2^(k+1) = 2i

The right child is simply one position after the left child: 2i + 1.

The Beauty of Binary

Deriving the parent formula:

The parent formula is the inverse of the child formulas. If node p has left child 2p and right child 2p+1, then:

The parent of an even index i is i/2
The parent of an odd index i is (i-1)/2

Both cases are captured by integer division: ⌊i/2⌋.

In programming terms, integer division of i by 2 automatically floors the result, handling both even and odd cases correctly.

Verification by example:

For index 11:

Parent: ⌊11/2⌋ = 5 ✓ (node 5 has children 10 and 11)
Left child: 2×11 = 22
Right child: 2×11 + 1 = 23

For index 6:

Parent: ⌊6/2⌋ = 3 ✓ (node 3 has children 6 and 7)
Left child: 2×6 = 12
Right child: 2×6 + 1 = 13

Deriving the 0-Based Formulas

The 0-based formulas are derived by offsetting the 1-based formulas. The relationship is:

If 1-based index is j, then 0-based index is i = j - 1, so j = i + 1

Deriving children:

In 1-based terms, left child of node j is 2j. Converting:

0-based parent index: i = j - 1, so j = i + 1
1-based left child: 2j = 2(i + 1) = 2i + 2
0-based left child: (2i + 2) - 1 = 2i + 1

Similarly, right child:

1-based right child: 2j + 1 = 2(i + 1) + 1 = 2i + 3
0-based right child: (2i + 3) - 1 = 2i + 2

1
2
3
4
5
6
7
              [0]                    Level 0: 1 node
             /   \
          [1]     [2]                 Level 1: 2 nodes
         /  \    /   \
       [3] [4] [5]   [6]              Level 2: 4 nodes
      /  \  / \  / \   / \
    [7][8][9][10][11][12][13][14]     Level 3: 8 nodes

Deriving parent:

In 1-based terms, parent of node j is ⌊j/2⌋. Converting:

0-based child index: i = j - 1, so j = i + 1
1-based parent: ⌊(i + 1)/2⌋
0-based parent: ⌊(i + 1)/2⌋ - 1

Simplifying: ⌊(i + 1)/2⌋ - 1 = ⌊(i + 1 - 2)/2⌋ = ⌊(i - 1)/2⌋

Verification by example:

For index 10 (0-based):

Parent: ⌊(10-1)/2⌋ = ⌊9/2⌋ = 4 ✓ (node 4 has children 9 and 10)
Left child: 2×10 + 1 = 21
Right child: 2×10 + 2 = 22

For index 5 (0-based):

Parent: ⌊(5-1)/2⌋ = ⌊4/2⌋ = 2 ✓ (node 2 has children 5 and 6)
Left child: 2×5 + 1 = 11
Right child: 2×5 + 2 = 12

Watch the Offset

Implementation Patterns

Let's translate these formulas into production-quality code with proper handling of edge cases.

Pattern 1: 0-based indexing (standard approach)

This is the most common pattern since most languages use 0-based arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Heap<T> {
    private data: T[] = [];
    
    // Parent index (returns -1 for root to indicate no parent)
    private parent(i: number): number {
        if (i === 0) return -1; // Root has no parent
        return Math.floor((i - 1) / 2);
    }
    
    // Left child index (may be beyond array bounds)
    private leftChild(i: number): number {
        return 2 * i + 1;
    }
    
    // Right child index (may be beyond array bounds)
    private rightChild(i: number): number {
        return 2 * i + 2;
    }
    
    // Check if index has a left child
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) < this.data.length;
    }
    
    // Check if index has a right child
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) < this.data.length;
    }
    
    // Check if index is a leaf node
    private isLeaf(i: number): boolean {
        return !this.hasLeftChild(i);
    }
}

Pattern 2: 1-based indexing with padding

Some implementations prefer the cleaner 1-based formulas by wasting index 0:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Heap1Based<T> {
    private data: (T | null)[] = [null]; // Index 0 is unused padding
    
    // Actual heap size (excluding padding)
    get size(): number {
        return this.data.length - 1;
    }
    
    // Parent index (returns 0 for root, which is invalid)
    private parent(i: number): number {
        return Math.floor(i / 2);
    }
    
    // Left child index
    private leftChild(i: number): number {
        return 2 * i;
    }
    
    // Right child index
    private rightChild(i: number): number {
        return 2 * i + 1;
    }
    
    // Check if index has a left child
    private hasLeftChild(i: number): boolean {
        return this.leftChild(i) <= this.size;
    }
    
    // Check if index has a right child
    private hasRightChild(i: number): boolean {
        return this.rightChild(i) <= this.size;
    }
    
    // Access element at index (1-based)
    private get(i: number): T {
        return this.data[i] as T;
    }
}

Choosing Your Convention

Handling Boundary Conditions

The formulas compute indices mathematically, but not every computed index is valid. Several boundary conditions must be handled:

1. Root has no parent

The root (index 0 in 0-based, index 1 in 1-based) has no parent. Applying the parent formula returns an invalid result:

0-based: parent(0) = ⌊(0-1)/2⌋ = ⌊-1/2⌋ = -1 (negative, clearly invalid)
1-based: parent(1) = ⌊1/2⌋ = 0 (which is the unused padding slot)

Always check before accessing the parent.

2. Leaves have no children

Leaf nodes have no children. The child formulas produce indices beyond the array bounds:

For a heap of size n, valid indices are 0 to n-1 (0-based) or 1 to n (1-based)
If leftChild(i) >= n, the node is a leaf
If leftChild(i) < n but rightChild(i) >= n, the node has only a left child

This last case is important: in a complete binary tree, the last internal node may have only a left child (the rightmost node on the second-to-last level).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class SafeHeap<T> {
    private data: T[] = [];
    
    // Safe parent access - returns undefined if no parent
    private getParentIndex(i: number): number | undefined {
        if (i <= 0) return undefined;
        return Math.floor((i - 1) / 2);
    }
    
    // Safe child access - returns undefined if no such child
    private getLeftChildIndex(i: number): number | undefined {
        const left = 2 * i + 1;
        return left < this.data.length ? left : undefined;
    }
    
    private getRightChildIndex(i: number): number | undefined {
        const right = 2 * i + 2;
        return right < this.data.length ? right : undefined;
    }
    
    // Get indices of all existing children (0, 1, or 2)
    private getChildIndices(i: number): number[] {
        const children: number[] = [];
        const left = this.getLeftChildIndex(i);
        const right = this.getRightChildIndex(i);
        if (left !== undefined) children.push(left);
        if (right !== undefined) children.push(right);
        return children;
    }
    
    // Find index of last non-leaf node
    // Useful for building heaps bottom-up
    private lastInternalNode(): number {
        return Math.floor(this.data.length / 2) - 1;
    }
    
    // Count of leaf nodes
    private leafCount(): number {
        return Math.ceil(this.data.length / 2);
    }
}

Leaf Node Count

In a complete binary tree with n nodes, exactly ⌈n/2⌉ are leaves and ⌊n/2⌋ are internal nodes. This is useful for algorithms like heapify that only need to process internal nodes.

3. Empty heap

An empty heap (n = 0) has no valid indices. All operations should check for this condition before accessing any index.

4. Single-element heap

With only the root (n = 1), there is no parent and no children. The root is simultaneously the minimum/maximum and a leaf.

Bit Manipulation Optimizations

The heap navigation formulas involve multiplication by 2, division by 2, and addition of small constants. These operations map directly to efficient bit operations:

Multiplication by 2: Left shift

2 * i = i << 1

Division by 2 (integer): Right shift

i / 2 = i >> 1 (for non-negative i)

Addition of 1: OR with 1

2i + 1 = (i << 1) | 1 (sets the lowest bit)

These aren't merely micro-optimizations—they reveal the underlying binary structure of heap indexing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 1-based indexing with bit operations
class BitHeap<T> {
    private data: T[] = [];
    
    // Parent: right shift by 1
    private parent(i: number): number {
        return i >> 1;
    }
    
    // Left child: left shift by 1
    private leftChild(i: number): number {
        return i << 1;
    }
    
    // Right child: left shift by 1, then set lowest bit
    private rightChild(i: number): number {
        return (i << 1) | 1;
    }
    
    // Check if node is a left child
    private isLeftChild(i: number): boolean {
        return (i & 1) === 0; // Even numbers are left children
    }
    
    // Check if node is a right child
    private isRightChild(i: number): boolean {
        return (i & 1) === 1 && i > 1; // Odd numbers (except 1) are right children
    }
    
    // Get sibling index
    private sibling(i: number): number {
        return i ^ 1; // XOR with 1 flips between left and right child
    }
}
 
// 0-based indexing equivalents
class BitHeap0Based<T> {
    private data: T[] = [];
    
    // Parent: (i-1) >> 1
    private parent(i: number): number {
        return (i - 1) >> 1;
    }
    
    // Left child: (i << 1) + 1
    private leftChild(i: number): number {
        return (i << 1) + 1;
    }
    
    // Right child: (i << 1) + 2
    private rightChild(i: number): number {
        return (i << 1) + 2;
    }
}

The XOR sibling trick:

For 1-based indexing, the sibling of node i is i XOR 1:

If i is even (left child), i XOR 1 = i + 1 (right sibling)
If i is odd (right child), i XOR 1 = i - 1 (left sibling)

This elegant property arises because left and right children are consecutive integers.

Modern Compilers Are Smart

Path from Root to Node

A powerful application of the index formulas is computing the path from the root to any node, or vice versa. This is useful for:

Debugging: Tracing how we reached a particular node
Understanding tree structure: Seeing the left/right decisions at each level
Advanced algorithms: Some heap variants need explicit path information

Path computation via binary representation (1-based):

For 1-based indexing, the binary representation of a node's index encodes its path from the root. Excluding the leading 1-bit:

0 means "go left"
1 means "go right"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Get path from root to node at index i (1-based)
function pathToNode(index: number): ('L' | 'R')[] {
    if (index <= 0) throw new Error('Invalid index');
    if (index === 1) return []; // Root has empty path
    
    const path: ('L' | 'R')[] = [];
    
    // Find the position of the highest set bit
    let temp = index;
    let bits: number[] = [];
    while (temp > 0) {
        bits.push(temp & 1);
        temp >>= 1;
    }
    bits.reverse();
    
    // Skip the leading 1, interpret remaining bits
    for (let i = 1; i < bits.length; i++) {
        path.push(bits[i] === 0 ? 'L' : 'R');
    }
    
    return path;
}
 
// Alternative: iterative parent traversal
function pathToNodeIterative(index: number): ('L' | 'R')[] {
    if (index <= 1) return [];
    
    const path: ('L' | 'R')[] = [];
    let current = index;
    
    while (current > 1) {
        const parent = current >> 1;
        if (current === parent * 2) {
            path.push('L');
        } else {
            path.push('R');
        }
        current = parent;
    }
    
    return path.reverse(); // Reverse to get root-to-node order
}
 
// Example usage:
// pathToNode(11) returns ['L', 'R', 'R']
// Binary of 11 is 1011: skip leading 1 -> 011 -> L, R, R

Index to Path Examples (1-Based)
Index	Binary	Path (excluding leading 1)
1	1	[] (root)
2	10	[L]
3	11	[R]
4	100	[L, L]
5	101	[L, R]
6	110	[R, L]
7	111	[R, R]
10	1010	[L, R, L]
13	1101	[R, L, R]

Depth Equals Bit Count Minus One

Comprehensive Formula Verification

To cement understanding, let's verify the formulas exhaustively for a small heap. This kind of manual verification is essential when first learning these relationships.

1
2
3
4
5
6
7
                    [0]
                  /      \
               [1]        [2]
              /   \      /    \
           [3]    [4]  [5]    [6]
          / \    / \   / \   / \
        [7][8] [9][10][11][12][13][14]

0-Based Index Relationships (Verified)
Node	Parent ⌊(i-1)/2⌋	Left 2i+1	Right 2i+2	Level ⌊log₂(i+1)⌋
0	— (root)	1	2	0
1	0 ✓	3	4	1
2	0 ✓	5	6	1
3	1 ✓	7	8	2
4	1 ✓	9	10	2
5	2 ✓	11	12	2
6	2 ✓	13	14	2
7	3 ✓	15 (OOB)	16 (OOB)	3
8	3 ✓	17 (OOB)	18 (OOB)	3
9	4 ✓	19 (OOB)	20 (OOB)	3
10	4 ✓	21 (OOB)	22 (OOB)	3
11	5 ✓	23 (OOB)	24 (OOB)	3
12	5 ✓	25 (OOB)	26 (OOB)	3
13	6 ✓	27 (OOB)	28 (OOB)	3
14	6 ✓	29 (OOB)	30 (OOB)	3

Observations from the table:

Every non-root node's parent formula produces the correct index
Nodes 7-14 (leaves) have children beyond the heap bounds (OOB = Out Of Bounds)
All nodes on the same level have consecutive indices
Parent indices are exactly half of child indices (accounting for the 0-based offset)
Siblings are always consecutive: (3,4), (5,6), (7,8), etc.

Build Your Own Table

Drawing out a small heap and computing all relationships by hand is one of the best ways to internalize these formulas. Do this once, and the formulas will feel natural rather than memorized.

Common Implementation Mistakes

Even simple formulas can harbor subtle bugs. Here are the most common mistakes when implementing heap navigation:

Common Mistakes to Avoid

•Mixing indexing conventions — Using 1-based parent formula with 0-based array indexing, or vice versa. Pick one and be consistent.
•Forgetting bounds checks — Accessing leftChild(i) without verifying it's within array bounds. Always check before dereferencing.
•Integer division confusion — In some languages, division operator behavior differs for negative numbers. Ensure you understand how your language handles '(-1)/2'.
•Off-by-one in heap size — Using 'heap.length' when you should use 'heap.length - 1', or vice versa. Document what 'size' means in your implementation.
•Treating root specially but incorrectly — The root (index 0 or 1) is special: it has no parent. But it's not special in other ways—don't add unnecessary special cases.
•Swapping formulas for parent/child — The child formula is NOT '2i - 1' for 0-based. It's '2i + 1'. Getting these backwards leads to incorrect heap structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class DefensiveHeap<T> {
    private data: T[] = [];
    
    private assertValidIndex(i: number, context: string): void {
        if (i < 0 || i >= this.data.length) {
            throw new Error(
                `Invalid heap index ${i} (size: ${this.data.length}) in ${context}`
            );
        }
    }
    
    private parentIndex(i: number): number {
        this.assertValidIndex(i, 'parentIndex');
        if (i === 0) {
            throw new Error('Root node has no parent');
        }
        return Math.floor((i - 1) / 2);
    }
    
    private leftChildIndex(i: number): number | undefined {
        this.assertValidIndex(i, 'leftChildIndex');
        const left = 2 * i + 1;
        return left < this.data.length ? left : undefined;
    }
    
    private rightChildIndex(i: number): number | undefined {
        this.assertValidIndex(i, 'rightChildIndex');
        const right = 2 * i + 2;
        return right < this.data.length ? right : undefined;
    }
    
    // Safe access with explicit undefined handling
    private getLeftChild(i: number): T | undefined {
        const idx = this.leftChildIndex(i);
        return idx !== undefined ? this.data[idx] : undefined;
    }
}

Defensive vs Performance

Summary: Navigating the Implicit Tree

Let's consolidate the key takeaways:

Key Takeaways

•1-based formulas are elegant: Parent = i/2, Left = 2i, Right = 2i+1. The binary structure of the tree maps to binary arithmetic.
•0-based formulas require offsets: Parent = (i-1)/2, Left = 2i+1, Right = 2i+2. More complex but aligns with standard array indexing.
•Boundary conditions are critical: Root has no parent, leaves have no children. Always check bounds before accessing.
•Binary representation encodes paths: For 1-based indexing, the bits of an index (after the leading 1) specify the path from root.
•Bit operations are equivalent: Multiplication/division by 2 are left/right shifts. This isn't just optimization—it reveals structure.
•Consistency is paramount: Pick one indexing convention and use it everywhere. Mixing conventions is a recipe for bugs.

What's next:

Page Complete

2 / 4