Binary Heap: The Array That Thinks It's a Tree

A tree hiding in an array

A binary heap is a complete binary tree — every level full except possibly the last, which fills left to right — stored with no pointers at all. Because the shape is always the same predictable shape, a node's children can be computed from its index alone, so the whole tree lives in one flat array:

parent(i) = (i - 1) >> 1
left(i)   = 2*i + 1
right(i)  = 2*i + 2

No child pointers, no parent pointers, no allocator calls per node. The array is dense and cache-friendly, which is a large part of why heaps beat pointer-based trees in practice even though both offer O(log n) operations on paper.

live demo · insertions and extractions reshuffling the array● LIVE

The heap property is weaker than it looks

A min-heap only guarantees that every parent is less than or equal to its children. That is not the same as being sorted — a heap says nothing about the order between two siblings, or between a node and its uncle. It only promises that the very top of the tree holds the minimum of everything below it. That weaker promise is the whole trick: enforcing it costs O(log n) per change instead of the O(log n) plus rebalancing a fully sorted structure would need.

Sift-up: inserting a value

Insertion appends the new value at the first free slot — the next position after the last leaf — which keeps the tree complete. That new leaf then sifts up: as long as it is smaller than its parent, swap with the parent and repeat. The tree has height ⌊log₂ n⌋, so at most that many swaps happen.

function siftUp(a, i) {
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (a[p] <= a[i]) break;
    [a[p], a[i]] = [a[i], a[p]];
    i = p;
  }
}

Sift-down: extracting the minimum

To remove the minimum, take the root's value to return, move the last element of the array into the root slot, shrink the array by one, and sift it down: repeatedly swap with the smaller of its two children until it is no longer larger than either. This also costs at most O(log n) swaps, and it is the operation Dijkstra's algorithm, A* and every discrete-event scheduler on this site call thousands of times per second.

function siftDown(a, i, n) {
  for (;;) {
    let s = i, l = 2*i+1, r = 2*i+2;
    if (l < n && a[l] < a[s]) s = l;
    if (r < n && a[r] < a[s]) s = r;
    if (s === i) break;
    [a[s], a[i]] = [a[i], a[s]];
    i = s;
  }
}

Building a heap in O(n), and heapsort

Calling sift-up n times to build a heap from scratch costs O(n log n). Floyd's 1964 heapify does better: start at the last non-leaf node and sift-down every node from the bottom up to the root. It looks like it should also cost O(n log n), but it doesn't — most nodes live near the bottom of the tree where their height, and therefore their maximum number of swaps, is tiny. Summing (height) times (number of nodes at that height) over the whole tree is a geometric series that converges, giving an O(n) total. Repeatedly swapping the root with the last element and sifting down the shrinking heap turns this into heapsort: an O(n log n), in-place, worst-case-guaranteed sort with no extra memory — though not a stable one, since equal keys can cross each other during the swaps.

d-ary heaps and where heaps actually show up

A binary heap is the d = 2 case of a more general d-ary heap: each node gets d children instead of 2. A larger d shrinks the tree's height (fewer sift-down levels) at the cost of comparing more children per level to find the smallest — 4-ary heaps are a common sweet spot for Dijkstra-style algorithms where decrease-key calls vastly outnumber extract-min calls. Beyond sorting, heaps back the open set in Dijkstra and A*, the ready queue in discrete-event and network simulators, k-way merges of sorted runs, and the classic two-heap trick for maintaining a running median: a max-heap for the lower half of the data and a min-heap for the upper half, kept within one element of each other.

Frequently asked questions

Is the root of a min-heap always the smallest, and is the array sorted?

The root is always the smallest value, but nothing else is sorted. A heap only guarantees that every parent is smaller than its children; it says nothing about the order between two children or between two cousins. That weaker guarantee is exactly what makes insert and extract-min cheap.

Why does building a heap from n items take O(n) and not O(n log n)?

Because sift-down cost depends on a node's height, not its depth, and most nodes in a complete tree are near the bottom with almost no height. Summing (height) * (nodes at that height) over the whole tree is a geometric series that converges to O(n), even though a single sift-down can cost O(log n).

When should I use a heap instead of a sorted array or a balanced BST?

Use a heap when you only ever need the current minimum (or maximum) and you insert and remove that extreme value repeatedly — Dijkstra's frontier, event-driven schedulers, k-way merges, top-k queries. A sorted structure keeps everything ordered, which costs more per update than a heap needs to pay.

Try it live

Everything above runs in your browser — open Binary Heap and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Binary Heap simulation