↩ back to Array-Backed Trees

Binary Heap

A binary search tree keeps every node fully ordered against its whole subtree — the price is a shape that depends entirely on insertion order, and can degrade to a straight line. A binary heap makes a different trade: it gives up almost all of that ordering, keeping only one rule — every parent is smaller than (or equal to) both its children (a min-heap; flip the comparison for a max-heap) — and in exchange the tree's shape is never in question. A heap is always a complete binary tree: every level is full except possibly the last, which fills strictly left to right. That fixed shape is what makes the whole thing work packed into a plain array, no pointers at all.

Try it

Insert a number and watch it bubble up from the end of the array toward the root, swapping with its parent until the parent is smaller. Extract the minimum and watch the last element drop into the root and sink back down, swapping with its smaller child until it settles. The tree drawing below is the array laid out by position — index 0 is the root, and a node at index i has children at 2i + 1 and 2i + 2.

Or skip inserting one at a time entirely: type a comma-separated array into the second field below and hit Heapify to bulk-build a heap from it in one bottom-up pass — the log line reports the actual swap count next to what building the same array via that many sequential inserts would have cost, so the O(n) vs O(n log n) gap in Pitfalls below is a real measured number, not just an asymptotic claim.

Core operations

• insert(x) — append x to the end of the array (the next open spot in the bottom level, keeping the tree complete), then sift up: while x is smaller than its parent, swap them, and repeat from the new position. O(log n), since the array's tree has height O(log n) by construction.
• extractMin() — the root (index 0) is always the minimum, by the heap rule. Save it, move the last element into the root position, shrink the array by one, then sift down: while the root is bigger than either child, swap with the smaller child, and repeat from the new position. Return the saved value. O(log n).
• peek() — return the root without removing it. O(1).
• buildHeap(arr) — bottom-up heapify: starting from the last non-leaf index (Math.floor(n/2) - 1) and working back to the root, sift each node down into place. Builds a valid heap from an existing array of n elements in O(n) total — cheaper than n calls to insert; see Pitfalls for why.

Notice neither operation ever needs to know where anything other than the root is. That's the whole point: a heap answers "what's the minimum?" in O(1) and "insert, remove the minimum" in O(log n), and refuses to answer almost anything else — see Pitfalls.

Why the array works: complete trees have no gaps

A binary search tree needs real pointers because its shape is unpredictable — a node might have a left child and no right child, or be missing entirely from one side. A heap's completeness guarantee rules that out: level 0 has exactly one slot, level 1 has exactly two, level d has exactly 2^d, all full except possibly the very last level, which fills left to right with no holes. That means every node's position can be computed from a single integer index, with no pointer needed to find it:

parent(i) = Math.floor((i - 1) / 2)
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

Insert always appends at the first open array slot, which is always exactly the next position completeness requires — no bookkeeping needed to find where the "next" leaf goes.

Reference implementation

class MinHeap {
  #a = [];

  size() { return this.#a.length; }
  peek() { return this.#a.length ? this.#a[0] : null; }

  // Bottom-up heapify: O(n), not n inserts' O(n log n) — see Pitfalls.
  static from(arr) {
    const h = new MinHeap();
    h.#a = arr.slice();
    for (let i = Math.floor(h.#a.length / 2) - 1; i >= 0; i--) h.#siftDown(i);
    return h;
  }

  insert(x) {
    this.#a.push(x);
    let i = this.#a.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.#a[parent] <= this.#a[i]) break;
      [this.#a[parent], this.#a[i]] = [this.#a[i], this.#a[parent]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.#a.length;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let smallest = i;
      if (left < n && this.#a[left] < this.#a[smallest]) smallest = left;
      if (right < n && this.#a[right] < this.#a[smallest]) smallest = right;
      if (smallest === i) break;
      [this.#a[i], this.#a[smallest]] = [this.#a[smallest], this.#a[i]];
      i = smallest;
    }
  }

  extractMin() {
    if (this.#a.length === 0) return null;
    const min = this.#a[0];
    const last = this.#a.pop();
    if (this.#a.length > 0) {
      this.#a[0] = last;
      this.#siftDown(0);
    }
    return min;
  }

  isValidHeap() {
    for (let i = 0; i < this.#a.length; i++) {
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < this.#a.length && this.#a[i] > this.#a[left]) return false;
      if (right < this.#a.length && this.#a[i] > this.#a[right]) return false;
    }
    return true;
  }
}

isValidHeap() is the same kind of sanity check as a binary search tree's inorder()-sortedness test: it's not needed for correct operation, but it's a cheap way to catch a broken invariant during testing. The interactive demo above uses an equivalent insert/extractMin, with the same comparisons and swaps, plus extra bookkeeping to record which indices were touched so the sift path can be highlighted. Verified with 25,000 randomized trials of interleaved insert/extract-min operations against a naive reference (a plain array, re-scanned for the minimum on every extraction), checking that every extracted value matches the reference's true minimum and that the heap property holds after every single operation — plus edge cases: empty extraction, single element, all-duplicate values, ascending-order insertion (heap property must still hold even though the shape looks sorted going in), and a full drain of 200 random values confirmed to come out in exactly sorted order (the "heapsort" property). See /tmp/heap_test.js, scratch, not committed.

The bulk-build/heapify demo added later uses pure standalone versions of the same sift-down logic (no DOM, no shared state with the insert/extract demo above) so they could be tested in isolation. Verified two ways: (1) this page's MinHeap.from(arr), retyped from the Reference Implementation above, against 25,000 randomized arrays of 0-59 elements, checking isValidHeap() holds, that the output is a permutation of the input (no elements dropped or duplicated by the swaps), and that fully draining the result via extractMin() reproduces the exact sorted input — plus edge cases (empty, single element, all-duplicate values, already-ascending input, already-descending input) and a 200-element full drain matching Array.sort() exactly; a separate pass over 2,000 random 500-element arrays measured an average of 365 heapify swaps against 611 swaps for the same elements via sequential insert, confirming the O(n) vs O(n log n) gap is real and not just asymptotic hand-waving. (2) the exact shipped heapifyArr/countInsertSwaps functions extracted verbatim out of the HTML, re-run through an equivalent 10,000-trial pass, zero mismatches, plus a deterministic check against the page's actual default bulk-build sample (the same nine numbers the preloaded insert-based sample above uses): heapify builds a valid heap in 7 swaps, sequential insert would have taken 8 — a modest gap at n=9, honestly reported as such, since the asymptotic difference only becomes dramatic at larger n (see the 500-element measurement above). See /tmp/heap_heapify_test.js and /tmp/heap_heapify_page_verify.js, scratch, not committed.

Pitfalls

A heap is not a search structure. The heap rule only constrains a node against its own parent — it says nothing about how a node compares to its sibling's subtree. That means the minimum is always at the root in O(1), but looking for an arbitrary value anywhere else requires an O(n) scan of the whole array, unlike a binary search tree's O(log n) search. Don't reach for a heap when you need "is X present" — reach for it when you only ever need "what's smallest right now."

Building a heap from n elements one insert at a time is slower than it needs to be. Calling insert n times costs O(n log n) total. A bottom-up heapify — start from the last non-leaf node and sift down each node in reverse array order back to the root — builds the same valid heap from an existing array in O(n), because most nodes in a complete tree are near the bottom, where a sift-down has almost no distance left to travel. Try it above: type a comma-separated array into the second field and hit Heapify — the log line reports the real swap count next to what building the same array via that many sequential inserts would have cost, so this isn't just an asymptotic claim. A real priority-queue library doing a one-time bulk load should always heapify instead of inserting one at a time.

Flipping a single comparison silently changes the invariant. Every line above compares with < or <= in a specific direction to keep the smallest value on top. Swap < for > in extractMin's sift-down and the code still runs, still looks like a heap, and still passes a quick eyeball check on a small example — it's just silently a max-heap now, or (if only one of the two comparisons is flipped) not a valid heap of either kind. This is exactly the kind of bug an isValidHeap() check catches instantly and a visual glance usually misses.

There's no cheap way to lower a key you don't already have the index of. Both operations above assume you're always working from the root — nothing here helps if you need to find some arbitrary element already inside the heap and reduce its value in place. Doing that safely means either an O(n) scan to find it first, or maintaining a separate value-to-index map alongside the array purely to make that lookup O(1). When an algorithm needs to do this often — repeatedly relaxing distances as it explores a graph, say — that gap is exactly what Fibonacci Heap exists to close: the same priority-queue interface, but with decreaseKey as a first-class amortized O(1) operation instead of an afterthought, at the cost of a heavier per-node structure and worse constant factors for everything else.

Where heaps show up

• Priority queues. Task schedulers, event-driven simulations, and "process the most urgent thing next" systems in general are almost always a heap under the hood — it's the standard way to implement the abstract priority-queue interface.
• Dijkstra's algorithm. Breadth-first search's shortest-path guarantee only holds on unweighted graphs; Dijkstra generalizes it to weighted graphs by always expanding the closest known node next — which means swapping BFS's plain queue for a heap-backed priority queue ordered by accumulated distance.
• Heap sort. Build a max-heap from the whole array in place, then extract the maximum repeatedly, and the output comes out sorted — an O(n log n) sort, in-place (unlike merge sort's O(n) buffer), with no worst-case O(n²) risk (unlike quicksort's bad-pivot case). The tradeoff is that it isn't stable and its constant factors tend to lose to a well-tuned quicksort in practice.
• Top-K and streaming median problems. "The k largest values seen so far," updated as new values stream in, is a classic fit for a heap of bounded size — far cheaper than re-sorting the whole stream on every update.

Complexity

Time: insert and extractMin are both O(log n) — always, not just on average, because the complete-tree shape guarantees height O(log n) no matter what order values arrive in (contrast with a binary search tree's worst-case O(n)). peek is O(1). Building a heap from n elements is O(n log n) via repeated insert or O(n) via bottom-up heapify (see Pitfalls). Searching for an arbitrary value is O(n) — no better than an unsorted array. Space: O(n), and unlike every tree on this site so far, zero pointers — just one flat array.

This site's guide, Choosing a Range Query Structure, sets this entry aside from the six it actually compares: a heap repeatedly pulls the current minimum (or maximum) out of a changing set, not a query over an arbitrary range of array positions.