A Tree With No Pointers: the Array-Backed Heap

"A heap is a tree on paper but an array in memory. No node objects, no left/right pointers — just arithmetic. That's the secret to why a 'tree' can be one of the fastest structures you'll use."

Completeness Buys You the Array

A binary heap is always a complete binary tree: every level is full except possibly the last, which fills strictly left to right. That shape has no gaps — and a tree with no gaps maps perfectly onto a flat array, level by level, with zero wasted slots. So a heap doesn't need node objects or pointers at all. It's just a Python list, and the 'tree' is a way of interpreting the indices.

Navigation Is Just Arithmetic

This is the formula from the binary-tree lesson, now earning its keep. For the element at index i:

its left child is at 2i + 1
its right child is at 2i + 2
its parent is at (i − 1) // 2

To 'climb the tree' toward the root, you keep doing i = (i-1)//2. To descend, you double-and-add. No pointer dereferencing, no allocations — moving around the tree is pure integer math on array indices. This is exactly why heap operations are so fast: the structure is contiguous, so the CPU cache stays warm (the array-vs-linked-list lesson, paying off yet again).

A complete binary tree packs gaplessly into an array: index i's children are 2i+1 / 2i+2, its parent is (i−1)//2. No nodes, no pointers — navigation is arithmetic, and the contiguous layout makes a heap cache-fast.

Why It Must Stay Complete

The completeness requirement isn't cosmetic — it's what keeps the array gapless and the height at exactly ⌊log₂ n⌋. That's why every heap operation appends to or removes from the end of the array (the next/last leaf position) and then restores order by moving elements up or down. If a heap were allowed to have holes, the index math would break and the height could grow. Completeness is the discipline that guarantees both the tidy array packing and the O(log n) height that makes everything fast.

Pippa's Confession

When Dad said "a heap is just a list," I didn't believe him — I'd drawn it as a tree with nodes and arrows. He had me number the tree positions level by level and write them into a flat array, then showed me 2i+1 always landed on the left child. The tree didn't disappear; it turned out to have been an array in a costume the whole time. That collapse — tree concept, array reality — is one of my favorite 'oh, it was simpler than I feared' moments in all of DSA.

Code

Navigating a heap with index arithmetic·python

# The heap is THIS list. The 'tree' is just how we read the indices.
heap = [1, 3, 2, 7, 4, 9, 5]
#  index: 0  1  2  3  4  5  6

def parent(i): return (i - 1) // 2
def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2

# Verify the tree structure lives entirely in arithmetic:
i = 0                                  # the root, value 1
print("root's children:", heap[left(i)], heap[right(i)])   # 3, 2
j = 4                                  # value 4
print("4's parent     :", heap[parent(j)])                  # 3

# Climb from a leaf to the root using only integer math (no pointers):
i = 6                                  # value 5, a leaf
path = [heap[i]]
while i > 0:
    i = parent(i)
    path.append(heap[i])
print("leaf-to-root path:", path)      # [5, 2, 1] — pure arithmetic navigation

Exercise

In an array-backed heap, the element at index 10 — what are the array indices of its two children and its parent? Then explain why a heap must always add new elements at the very end of the array (the next leaf spot) rather than wherever there's space, and what would break otherwise.

Hint

Children of 10: 2·10+1=21 and 22; parent: (10−1)//2 = 4. New elements must go at the end to preserve completeness (no gaps); a hole in the middle would break the 2i+1/2i+2 index math and let the height grow beyond log n.

Completeness Buys You the Array

Navigation Is Just Arithmetic

Why It Must Stay Complete

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0