The heap structure
Why a complete binary tree packs into an array, and the one invariant that makes it a heap. · 9 min read
Concept
A binary heap is a complete binary tree — every level is full except possibly the last, which fills left to right — that satisfies the heap property. In a min-heap, every node is ≤ both its children, so the smallest value is always at the root. (A max-heap is the mirror image.)
A heap is not sorted and it is not a binary search tree. It only guarantees the root is the extreme value; siblings and cousins are unordered. That weaker promise is exactly what lets it stay cheap to maintain.
The array trick
Because the tree is complete, we never need pointers — we pack it into an array by reading level by level. For the node at index i:
parent(i) = (i - 1) // 2
left(i) = 2*i + 1
right(i) = 2*i + 2level L holds 2^L nodes, starting at index 2^L − 1— Completeness means each level is packed contiguously.a node at index i has children at 2i+1, 2i+2— Doubling moves you one level down.⟹ no gaps, no pointers— The array *is* the tree.
Result: O(n) space, pointer-free
Interactive visualization: Min-heap: insert sifts up, extract-min sifts down — step through it frame by frame on this page.
Complexity target
The tree has height ⌊log₂ n⌋, so the operations that walk a root-to-leaf path — insert and extract — are O(log n). Reading the min (the root) is O(1). Building a heap from n items is O(n) with the bottom-up method (a classic surprise).