The Binary Heap: Storing a Complete Tree in an Array

A binary heap is the standard concrete implementation of a heap: a complete binary tree stored not with nodes and pointers but inside an ordinary array. Because a complete tree has no gaps, level-order traversal maps perfectly onto consecutive array slots — so we can navigate from any node to its parent or children with plain arithmetic. This page is about that array layout; the introduction covers the heap property, and heap operations covers how we keep it valid.

Why a complete tree fits an array

A tree is complete when every level is full except possibly the last, which is filled from the left with no holes. That “no holes” guarantee is the magic: if you write the nodes out level by level, left to right, you get a dense array with no wasted slots.

index:   0   1   2   3   4   5
value: [ 1 , 3 , 2 , 7 , 4 , 5 ]

           1            <- index 0
         /   \
        3     2         <- indices 1, 2
       / \   /
      7   4 5           <- indices 3, 4, 5

The array and the tree are two views of the same thing. There are no left/right pointers to store or follow — saving memory and giving great cache locality (neighbors in the tree are neighbors in memory).

The index arithmetic

For a node at 0-based index i:

• parent(i) = (i - 1) / 2
• left child(i) = 2*i + 1
• right child(i) = 2*i + 2

A child exists only if its computed index is < size. The element at index 0 is the root (the min or the max). The last element is at index size - 1, and the last non-leaf node sits at index size/2 - 1 — useful when building a heap.

#include <vector>
struct BinaryHeap {
    std::vector<int> a;           // the backing array IS the heap
    int size() const { return (int)a.size(); }
    int parent(int i) const { return (i - 1) / 2; }
    int left(int i)   const { return 2 * i + 1; }
    int right(int i)  const { return 2 * i + 2; }
    bool hasLeft(int i)  const { return left(i)  < size(); }
    bool hasRight(int i) const { return right(i) < size(); }
    int peek() const { return a[0]; }   // root, O(1)
};

import java.util.*;

class BinaryHeap {
    private final List<Integer> a = new ArrayList<>(); // backing array
    int size()        { return a.size(); }
    int parent(int i) { return (i - 1) / 2; }
    int left(int i)   { return 2 * i + 1; }
    int right(int i)  { return 2 * i + 2; }
    boolean hasLeft(int i)  { return left(i)  < size(); }
    boolean hasRight(int i) { return right(i) < size(); }
    int peek()        { return a.get(0); }   // root, O(1)
}

class BinaryHeap {
  constructor() { this.a = []; }     // backing array IS the heap
  size()       { return this.a.length; }
  parent(i)    { return (i - 1) >> 1; }
  left(i)      { return 2 * i + 1; }
  right(i)     { return 2 * i + 2; }
  hasLeft(i)   { return this.left(i)  < this.size(); }
  hasRight(i)  { return this.right(i) < this.size(); }
  peek()       { return this.a[0]; }  // root, O(1)
}

class BinaryHeap:
    def __init__(self):
        self.a = []                 # backing list IS the heap
    def size(self):     return len(self.a)
    def parent(self, i): return (i - 1) // 2
    def left(self, i):   return 2 * i + 1
    def right(self, i):  return 2 * i + 2
    def has_left(self, i):  return self.left(i)  < self.size()
    def has_right(self, i): return self.right(i) < self.size()
    def peek(self):     return self.a[0]   # root, O(1)

For beginners: Reading the root is a[0] — that’s the whole reason heaps exist. You never search; the answer is always at the front.

Walking the tree by hand

Take the array [1, 3, 2, 7, 4, 5] and start at index 3 (value 7):

• parent(3) = (3 - 1) / 2 = 1 → value 3. Correct: 7’s parent is 3.
• left(1) = 2*1 + 1 = 3 → value 7, and right(1) = 4 → value 4. Correct: 3’s children are 7 and 4.

No traversal, no pointer chasing — just multiply, add, or shift.

Where the layout shines (and where it doesn’t)

• Strengths: O(1) root access, O(log n) insert/extract, contiguous memory, trivial to grow with a dynamic array.
• Limitation: the array layout only works because the tree is complete. The moment you’d need an arbitrary-shaped tree (like a BST after deletions), you go back to nodes and pointers.

Going deeper: A heap with a d-ary branching factor (each node has d children) generalizes the math to parent = (i-1)/d, child_k = d*i + k. Larger d shortens the tree (faster inserts) at the cost of slower extracts. Binary (d = 2) is the common sweet spot.

Now you can store the tree — next, learn how to keep the heap property intact with insert, extract, and build-heap.