We've established the heap property—the ordering invariant that places the extreme element at the root. But ordering alone doesn't guarantee efficiency. Consider a degenerate tree where every node has only a left child: it could satisfy the heap property while being essentially a linked list, with O(n) height and O(n) operations.

The complete binary tree structure is the second invariant that prevents this catastrophe. It constrains the tree's shape, not its values, ensuring optimal height and enabling a remarkable property: we can represent the entire tree using just an array, with no pointers at all.

This page explores the complete binary tree in depth—what it is, why heaps require it, and how this shape unlocks the array representation that makes heaps memory-efficient and cache-friendly.

Let's establish the precise definition:

Definition (Complete Binary Tree): A binary tree is complete if all levels except possibly the last are completely filled, and all nodes in the last level are as far left as possible.

This deceptively simple definition has profound implications. Let's unpack each part:

Visual Examples:

Complete Binary Tree (valid):

         A              Level 0: 1 node (full)
       /   \           
      B     C          Level 1: 2 nodes (full)
     / \   /
    D   E F            Level 2: 3 nodes (left-filled)

NOT Complete (gap in last level):

         A              Level 0: 1 node (full)
       /   \           
      B     C          Level 1: 2 nodes (full)
     /     / 
    D     E   F        Level 2: gap between D and E ✗

NOT Complete (missing node in non-last level):

         A              Level 0: 1 node (full)
       /              
      B                Level 1: only 1 node ✗
     / 
    D   E              This level has nodes but level 1 is incomplete

The most important consequence of completeness is the height guarantee:

Height Theorem: A complete binary tree with n nodes has height exactly ⌊log₂ n⌋.

This is the optimal height for any binary tree with n nodes—you cannot have a shorter binary tree containing n nodes.

Why Height Matters for Performance:

Heap operations (insert, extract, bubble-up, bubble-down) all traverse a path from a node to the root or to a leaf. The length of the longest such path is exactly the height of the tree.

This is extraordinary. Even for a billion elements, heap operations involve at most 30 comparisons and swaps. The completeness property guarantees this bound—without it, a degenerate tree could require n operations.

Contrast: Non-Complete BST Worst Case

Consider inserting sorted data into an unbalanced BST: 1, 2, 3, 4, 5, ..., n

The result is a degenerate tree (linked list):

1
 
  2
   
    3
     
      ...
       
        n

Height = n - 1, operations are O(n). This is why BSTs need explicit balancing (AVL, Red-Black). Heaps sidestep this entirely: the completeness constraint is baked into the structure, eliminating degenerate cases by definition.

The completeness property creates a deterministic filling pattern that's key to understanding heaps:

Nodes fill the tree in this order:

1. Root (level 0)
2. Left child of root, then right child of root (level 1)
3. Children of left child (left then right), then children of right child (left then right) (level 2)
4. And so on...

This is exactly breadth-first (level-order) filling. If we number positions in this order starting from 0, we get:

                 0                   Level 0: position 0
              /     
            1         2              Level 1: positions 1, 2
          /   \     /   
         3     4   5     6           Level 2: positions 3, 4, 5, 6
        / \   / 
       7   8 9  10                   Level 3: positions 7, 8, 9, 10

The positions 0, 1, 2, 3, 4, 5, ... correspond exactly to array indices!

This is the insight that enables array-based heap representation: a complete binary tree with nodes at positions 0 through n-1 maps directly to an array of size n.

Deriving the Index Formulas:

Left Child Formula (2i + 1): At each level, the number of positions doubles. Position i has seen i node positions before it. The number of positions at or before level containing i is about 2i. The left child is the first of the two children, at position 2i + 1.

More formally: if a node is at position i, all positions 0 to i are filled. The children of positions 0 to i-1 occupy positions 1 to 2(i-1)+2 = 2i. So position i's left child is at 2i + 1.

Parent Formula ((i-1)/2): This is the inverse of the child formulas. Given child position i:

• If i = 2p + 1 (left child of p), then p = (i - 1) / 2
• If i = 2p + 2 (right child of p), then p = (i - 2) / 2 = (i - 1) / 2 (integer division)

Both cases give ⌊(i - 1) / 2⌋. This elegant unification is because consecutive children of the same parent differ by 1, and integer division absorbs the difference.

The completeness property enables one of the most elegant representations in all of computer science: storing a tree as a contiguous array with no pointers.

Traditionally, trees require:

• Each node to store 2-3 pointers (left child, right child, maybe parent)
• Each pointer: 8 bytes on 64-bit systems
• Overhead per node: 16-24 bytes just for structure
• Nodes scattered in memory: poor cache locality

With array representation:

• No pointers at all—parent/child relationships are arithmetic
• Zero structural overhead
• Contiguous memory: excellent cache locality
• Simpler implementation: no malloc/free, no null checks

Example: Array Representation

Consider this heap:

         90
       /    
     75      80
    /  \    /
   60  55  70

As an array: [90, 75, 80, 60, 55, 70]

The relationships:

• Index 0 (90): children at 1 (75) and 2 (80) ✓
• Index 1 (75): parent at 0 (90), children at 3 (60) and 4 (55) ✓
• Index 2 (80): parent at 0 (90), children at 5 (70) and 6 (doesn't exist: out of bounds) ✓

The array IS the heap. No additional structure needed.

Theoretical analysis tells us heaps are O(log n). But on real hardware, constant factors matter enormously, and cache locality is where heaps truly shine.

The Memory Hierarchy Reality:

• L1 cache access: ~1 nanosecond
• L2 cache access: ~3-4 nanoseconds
• L3 cache access: ~10-20 nanoseconds
• Main memory (RAM): ~50-100 nanoseconds

A cache miss is 50-100x slower than a cache hit. Data structures that maximize cache hits vastly outperform those that don't, even with identical big-O complexity.

Why Array-Based Heaps Win:

1. Spatial Locality: When we access index i, the CPU loads a cache line (64 bytes typically) containing i and its neighbors. For a bubble-up operation: indices i, parent(i), parent(parent(i)), ... are often on the same or adjacent cache lines near the root.

2. Sequential Access in Heapify: Building a heap via bottom-up heapify accesses array elements largely in order (indices n/2 down to 0). This is cache-optimal—each cache line is loaded once and used completely.

3. Predictable Access Patterns: The CPU's prefetcher can anticipate heap access patterns because they're arithmetically determined. It preloads the next cache line before you need it.

Contrast with Pointer-Based Trees:

• Each node could be anywhere in memory
• Following a pointer = potential cache miss
• Modern CPUs can't prefetch effectively
• Dynamic allocation fragments nodes across memory

Quantifying the Difference:

Consider extracting the minimum 1 million times from a 1-million element heap:

Array-based heap:

• ~20 swaps per extraction × ~4 bytes per comparison (stays in cache)
• Mostly L1/L2 hits: ~3 ns per operation
• Total: ~20 × 3 ns × 1M = 60 million ns = 60 ms

Pointer-based tree (hypothetical):

• Same ~20 swaps per extraction
• Each pointer dereference: potential 50 ns cache miss
• If half are misses: ~20 × 25 ns × 1M = 500 million ns = 500 ms

Same algorithm, 8x slower—purely from memory access patterns.

This is why production heap implementations universally use arrays. The completeness property makes this possible.

Completeness isn't just an initial property—it must be maintained as elements are inserted and removed. The heap operations are specifically designed to preserve this invariant.

Insertion: Always at the Next Position

When inserting a new element, it always goes at index size (the current size of the heap, 0-indexed). This is the 'next' position in level-order.

Before (size = 6):          After insert (size = 7):
      [0]                         [0]
     /   \                       /   
   [1]   [2]                   [1]   [2]
   / \   /                     / \   / 
 [3][4][5]                   [3][4][5][6] ← new element

The new element is placed at index 6, which is the leftmost empty position at the current level. Completeness preserved.

The new element might violate the heap property (be larger than its parent in a max-heap), so we bubble it up. But the shape remains complete throughout—we never create gaps.

Extraction: Remove Root, Replace with Last

When extracting the root (max or min), we:

1. Take the value at the root (index 0)
2. Move the last element (index size - 1) to the root
3. Decrease size by 1
4. Bubble down to restore heap property

Before (size = 7):          After extract (size = 6):
      90                         75 ← moved from last position
     /  \                       /  
   75    80                   60    80
   / \   / \                 / \   /
 60 55 70  40               45 55 70
 /
45 ← last element

The last element fills the gap at the root, preserving completeness. It's now at the wrong position (violates heap property), but bubbling down fixes that while maintaining the complete shape.

The heap's two invariants—shape (completeness) and order (heap property)—work together in a beautiful way. Neither alone is sufficient; together they enable everything heaps can do.

The Synergy:

• Completeness ensures that bubbling up/down traverses at most O(log n) levels
• Heap property ensures that bubbling up/down eventually terminates (the correct position is found)
• Together: O(log n) operations that maintain both invariants

Thought Experiment: What If We Relaxed Each?

Without completeness (arbitrary tree shape):

• Height could be O(n) → operations become O(n)
• No clean array representation → need pointers
• This is just a 'heap-ordered tree', not a heap

Without heap property (just complete binary tree):

• Root is arbitrary → no efficient extreme access
• Still have the array structure, but no ordering benefit
• This is just a complete binary tree, not a heap

The heap's power comes from both constraints working in concert.

We've explored the complete binary tree structure—the shape invariant that makes heaps efficient and practical. Let's consolidate the key insights:

What's next:

With both invariants understood—heap property (ordering) and completeness (shape)—we now examine why shape matters from a performance perspective. The next page synthesizes how these properties combine to guarantee the efficiency that makes heaps indispensable.