Array-Based Heap Implementation

When you first learn about trees in computer science, the natural implementation uses nodes with explicit pointers—each node stores references to its children, and perhaps to its parent. This approach is intuitive: it mirrors how we draw trees on paper, with arrows connecting boxes. Yet for one specific and critically important type of tree, this pointer-based approach is not just unnecessary—it's suboptimal.

The binary heap, built on the foundation of a complete binary tree, possesses a structural regularity so profound that we can eliminate pointers entirely. Instead of storing a tree as a collection of nodes linked by references, we can store it as a simple, contiguous array. The tree structure becomes implicit—encoded not in explicit connections, but in the mathematical relationship between array indices.

This insight transforms heap implementation from a graph-like structure into something far more elegant and efficient. Understanding this implicit representation is fundamental to mastering heaps and unlocks performance characteristics that make heaps indispensable in systems ranging from operating system schedulers to real-time event processing.

Before diving into array representation, we must firmly establish why this technique works specifically for complete binary trees and not for arbitrary trees.

Recall the definition of a complete binary tree:

A complete binary tree is a binary tree where:

1. Every level except possibly the last is completely filled
2. All nodes in the last level are as far left as possible

This definition might seem like an arbitrary constraint, but it carries profound implications. A complete binary tree has no gaps. When you traverse the tree level by level, from left to right (level-order traversal), you encounter a continuous sequence of nodes with no holes until you reach the final, possibly incomplete level—and even there, nodes are packed to the left.

Why arbitrary trees don't work:

Consider a binary tree that is not complete—perhaps a tree where the root has only a left child, which has only a right child, which has only a left child. If we tried to use level-order numbering:

• Position 0: Root ✓
• Position 1: Left child of root ✓
• Position 2: Right child of root ✗ (doesn't exist)
• Position 3: Left child of position 1 ✗ (doesn't exist)
• Position 4: Right child of position 1 ✓
• ...

We'd have gaps—positions 2 and 3 are empty. To represent this tree in an array, we'd need to either:

1. Store null values in the gaps, wasting space and complicating logic
2. Use a sparse representation with explicit position markers, reintroducing complexity

Neither option preserves the elegant simplicity we're seeking. Completeness eliminates gaps, and eliminating gaps enables direct indexing.

The array representation of a complete binary tree is based on level-order numbering—also known as breadth-first numbering. Starting from the root, we assign each node an index based on its position in a breadth-first traversal.

Let's establish this concretely with an example. Consider a complete binary tree with 10 nodes:

The level-order principle:

At each level k, the first node has index 2^k - 1 (0-based), and there are at most 2^k nodes. The levels fill sequentially:

• Level 0: 1 node (index 0)
• Level 1: 2 nodes (indices 1, 2)
• Level 2: 4 nodes (indices 3, 4, 5, 6)
• Level 3: 8 nodes (indices 7, 8, ..., 14, if fully filled)

This exponential growth of level capacity is intrinsic to binary trees, and the level-order numbering captures this structure perfectly.

The mapping to array:

Given the level-order numbering, the array representation is trivial. We simply place each node's value at its corresponding index:

Observe the elegance: No pointers, no node objects, no memory overhead per node—just a flat array of values. The tree structure is implicit in the positions. Index 0 is the root. Index 1 is the left child of the root. Index 2 is the right child of the root. And so on.

This isn't merely a storage optimization; it's a fundamentally different representation paradigm. The tree exists in the array, but only through the lens of index arithmetic.

To truly internalize array-based heap representation, you must develop the ability to see the tree within the array. This mental skill—translating between linear array view and hierarchical tree view—is essential for debugging, tracing algorithms, and building intuition.

Mental model 1: Layered segments

Think of the array as divided into segments, one per tree level:

Mental model 2: Binary expansion

A powerful way to understand the implicit structure is through binary representation of indices. In 1-based indexing, the path from the root to any node corresponds exactly to the binary representation of its index (excluding the leading 1-bit):

• After the leading 1, a 0-bit means "go left"
• A 1-bit means "go right"

For example, index 11 in binary is 1011:

• Leading 1: start at root
• 0: go left
• 1: go right
• 1: go right

Following this path from the root gives you the node at index 11.

Mental model 3: Parent-child locality

Another useful observation: nodes that are close in the tree tend to be close in the array. Specifically:

• A node's children are always nearby (at indices 2i and 2i+1 for 1-based)
• Nodes on the same level are contiguous in the array
• Moving down one level roughly doubles the index
• Moving up one level roughly halves the index

This locality has direct performance implications that we'll explore when discussing cache behavior.

The implicit tree structure isn't magic—it rests on precise mathematical relationships. Let's formalize the key properties that make this representation work.

Property 1: Level calculation

A node at index i (0-based) resides at level ⌊log₂(i + 1)⌋.

For 1-based indexing, a node at index i resides at level ⌊log₂(i)⌋.

This follows from the observation that:

• Level 0 contains index 0 (or 1 in 1-based)
• Each subsequent level doubles in capacity
• The first index of level k is 2^k - 1 (0-based) or 2^k (1-based)

Property 2: Position within level

Given a node at index i (0-based), its position within its level (0-indexed from left) is:

position = i - (2^level - 1) = i - 2^⌊log₂(i+1)⌋ + 1

This calculation subtracts the starting index of the level from the node's index.

Property 3: Subtree boundaries

For a node at index i, its subtree contains specific index ranges. The descendants of node i span a contiguous range that can be calculated based on the node's level and position. While the exact formulas are complex, the key insight is that subtrees map to predictable array segments.

Property 4: Height relationship

For a heap with n elements, the height h is ⌊log₂(n)⌋. This is because:

• We need at least 2^h slots to reach level h
• Level h can contain up to 2^h nodes
• So height = ⌊log₂(n)⌋

This logarithmic height is why heap operations achieve O(log n) time complexity—they traverse at most h + 1 levels.

You might wonder: "Pointer-based trees work fine for other structures. Why is array representation better for heaps?"

The answer involves multiple dimensions of improvement: memory, performance, simplicity, and cache behavior. Let's examine each.

Memory overhead comparison:

Consider storing 1 million 32-bit integers in a heap:

Pointer-based (with parent pointers):

• Per node: 4 bytes (value) + 8 bytes (left) + 8 bytes (right) + 8 bytes (parent) = 28 bytes
• Plus allocation overhead: ~16 bytes per malloc (header + alignment)
• Total: ~44 bytes × 1M = ~44 MB
• Plus object metadata if using a language with managed memory

Array-based:

• Per element: 4 bytes (value)
• One allocation for entire array
• Total: 4 bytes × 1M = 4 MB

That's an 11x memory reduction. For memory-constrained systems or heaps with billions of elements, this difference is transformative.

Perhaps the most significant performance benefit of array-based heaps comes from memory contiguity. When heap elements are stored in a single, contiguous array, memory access patterns become highly predictable.

CPU cache fundamentals:

Modern CPUs don't fetch individual bytes from RAM; they fetch cache lines—typically 64 bytes at a time. When you access one element, the CPU speculatively loads its neighbors into cache. This prefetching is:

• Brilliant for arrays: Accessing element i likely brings elements i+1 through i+15 (for 4-byte integers) into cache. Subsequent accesses are nearly instant.
• Terrible for scattered pointers: Following a pointer to a heap-allocated node brings one node into cache. The next pointer might jump to a completely different memory region—a cache miss.

Heap operations and cache behavior:

Consider a bubbleUp operation (moving an element up the tree after insertion):

The prefetching bonus:

Because array access patterns are predictable (we're doing simple arithmetic on indices), the CPU's hardware prefetcher can anticipate future accesses and load them proactively. Pointer chasing is fundamentally unpredictable—the CPU can't know where the next pointer leads without dereferencing it.

This is why array-based data structures often outperform linked structures even when both have the same asymptotic complexity. The O(log n) of an array heap and a pointer-based heap are the same in theory, but the constants differ significantly in practice.

Beyond performance, array-based heaps are simply easier to implement correctly. The cognitive load of managing pointers, handling edge cases at tree boundaries, and maintaining parent references disappears.

No pointer management:

• No malloc/free for individual nodes
• No risk of memory leaks or dangling pointers
• No null checks for missing children
• No special cases for root (which has no parent pointer)

Simpler swaps:

Heap operations fundamentally involve swapping elements. Compare the swap implementations:

Error resistance:

Pointer-based tree code is notoriously error-prone. Off-by-one errors in index calculations are frustrating but debuggable. Dangling pointer bugs or corrupted tree structure can be catastrophic and nearly impossible to diagnose.

The array-based approach trades pointer complexity for arithmetic simplicity. Getting the parent formula wrong produces wrong answers but doesn't corrupt memory or crash the program.

While array-based heap representation is overwhelmingly advantageous for the heap use case, intellectual honesty demands we acknowledge its limitations.

Limitation 1: Only works for complete binary trees

This representation is not general-purpose. If you need a tree with arbitrary shape—perhaps a BST that becomes unbalanced, or a tree built from specific structural requirements—array representation either doesn't work or wastes significant space.

Limitation 2: Resizing overhead

When the heap grows beyond array capacity, we must allocate a new, larger array and copy all elements. This is an O(n) operation. While amortized analysis shows this averages to O(1) per insertion (by doubling capacity), individual operations can spike in latency.

Pointer-based trees never need bulk copying—each insertion allocates one node.

Limitation 3: Not suitable for persistent data structures

If you need to maintain historical versions of your heap (persistent or immutable heaps), array representation is problematic. Modifications require full array copies to preserve old versions. Pointer-based trees support path-copying techniques for O(log n) persistent updates.

Limitation 4: Merge operation

Merging two array-based heaps requires O(n) time (combine arrays, then heapify). Specialized mergeable heaps (like Fibonacci heaps or Binomial heaps) use pointer-based representations to achieve O(1) or O(log n) merge.

The bottom line:

For standard priority queue use cases—where we insert elements, extract the minimum/maximum, and occasionally peek—array-based heaps are unambiguously superior. The limitations only matter for specialized use cases that most applications never encounter.

We've established the foundational insight that makes array-based heaps possible: complete binary trees have a gap-free level-order numbering that maps perfectly to array indices. This isn't just a cute observation—it's the basis for one of the most practically important data structure implementations.

Let's consolidate our key takeaways:

What's next:

Now that we understand why we can represent heaps as arrays, we need the precise formulas for navigating the implicit tree. The next page covers the parent and child index formulas—the arithmetic that lets us traverse the tree structure encoded in the array. These formulas are simple, but understanding their derivation and selecting the right indexing convention (0-based vs 1-based) matters for correct implementation.