Binary Heap — Trees

Overview

What this concept solves

A binary heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is ≤ both its children; in a max-heap every parent is ≥ both. 'Complete' means every level is fully filled except possibly the last, which fills left to right. That shape constraint is what makes the array mapping work — there are no gaps, so the children of node i sit at exactly 2i + 1 and 2i + 2, and the parent of node i is at Math.floor((i - 1) / 2).

Because the shape is perfectly predictable, a heap needs no pointers, no left/right references, no node objects — just a plain array. The root lives at index 0. Its two children live at 1 and 2. Their children live at 3, 4, 5, 6. When you draw that array as a tree you get the visual above; when you look at the tree you can always read off the array index from the node's position. Every operation you do on the tree — insert, extract, bubble-up, sift-down — translates to arithmetic on array indices. This is what makes the heap so cache-friendly and compact in practice.

The heap is purpose-built for one thing: fast access to the extreme element. peek is O(1) — the min (or max) is always at index 0. insert is O(log n) — append to the end, then swap your way up. extractRoot is O(log n) — grab index 0, replace it with the last element, then swap your way down. What the heap cannot do efficiently is answer 'where is the element with key k?' — finding an arbitrary key requires scanning the whole array, O(n). It is not a search tree. Use it when you need the extreme end of a collection repeatedly and quickly, not when you need arbitrary lookups.

Mechanics

How it works

Bubble-up (insert)

Append the new value to the end of the array. Call its index i.
Compare arr[i] with its parent at arr[Math.floor((i - 1) / 2)].
If the heap property is violated (e.g. arr[i] < arr[parent] in a min-heap), swap the two.
Set i = parent index and repeat from step 2.
Stop when the root is reached or no swap is needed — the property holds.

Index arithmetic: commit these to muscle memory

Children of node i: left = 2i + 1, right = 2i + 2. Parent of node i: Math.floor((i − 1) / 2). These three formulas are the tree structure — every heap operation runs on them and nothing else. There is no node.left, no node.parent pointer anywhere in the code.

Sift-down (extract root)

Save arr[0] — that's the value being returned.
Move the last element (arr[size - 1]) to index 0, then shrink the array by one.
Now arr[0] may violate the heap property. Compare it with its two children at 2i + 1 and 2i + 2.
In a min-heap, swap with the smaller child if that child is smaller than the current node. (Max-heap: swap with the larger child.)
Repeat from step 3 with the new index until both children are ≥ the current node, or a leaf is reached.

O(n) build-heap — Floyd's trick

Inserting n elements one at a time costs O(n log n). But if you already have all the values, you can do better: load them into the array in any order, then call siftDown on every internal node from index Math.floor(n / 2) − 1 down to 0. Each sift-down is cheap for nodes near the bottom (short path), and there are exponentially fewer nodes near the top. The sum works out to O(n) — a factor of log n faster than repeated insertion. This is Floyd's 1964 buildHeap and it is the foundation of heapsort.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Binary Heap

About this simulation

A complete binary tree drawn alongside its backing array — same data, two views at once. Toggle between Min-heap and Max-heap to see the heap property flip and the entire structure re-heapify. Type any number and press Insert to watch the new leaf bubble up through parent swaps; press Extract root to pop the top and watch siftDown restore order. The Speed slider controls how fast each swap animates. Shortcuts: Random fills a fresh heap in one shot; Reset clears everything. The demo buttons — Insert 1 → bubble all the way up and Extract root → watch sift-down — run pre-scripted sequences so you can trace every index formula in real time. Stats panel tracks size, height, total swaps, and current root.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Insert 1 → bubble all the way up

Click the "Insert 1 → bubble all the way up" demo button. In a max-heap, 1 is the smallest possible value and will stay put near the leaves — but switch to Min-heap first, then run it. Now 1 is the minimum, so it will bubble up through every level: leaf → internal node → root in ⌊log₂ n⌋ swaps. Watch both the tree view (the highlighted node climbing) and the array panel (the index arithmetic shifting values left). The swaps counter in the stats panel will tick once per level. Notice the parent-index formula Math.floor((i − 1) / 2) running at each step.

try 02

Extract root → watch sift-down

Press "Extract root → watch sift-down". The root vanishes, the last array element teleports to index 0, and now the heap property is violated at the top. siftDown kicks in: the new root is compared with both children; it swaps with the smaller child (min-heap) and descends. At each level the prototype highlights the two children being compared and the winning swap. Count the swaps against the tree height shown in the stats — sift-down takes at most height swaps, and height = ⌊log₂ n⌋. A heap of 1 million elements needs at most 20 swaps to restore order.

try 03

Toggle Min-heap vs Max-heap — watch the re-heapify

Fill the heap with Random so you have 10–15 nodes. Now toggle from Max-heap to Min-heap. The structure isn't sorted in the new sense, so the prototype re-runs buildHeap (Floyd's O(n) bottom-up pass) on the existing array. Watch every internal node sift down in reverse order — rightmost internal node first, root last. The tree re-draws itself with every swap. Toggle back and forth a few times; the root always settles to the global min (min-heap) or global max (max-heap) by the end of the pass. This is how you'd switch policies in a priority queue without rebuilding from scratch.

try 04

Free play — break it yourself

Reset and manually insert values in sorted ascending order: 1, 2, 3, 4, 5, 6, 7 into a Min-heap. Each insert does zero swaps — the values already satisfy the heap property, so bubble-up terminates immediately every time. Now try the same sequence into a Max-heap: each insert will bubble all the way to the root because every new value is larger than the current root. Compare the swap counters between the two runs. This shows that heap insert's O(log n) is a worst case — the actual cost depends on the input order. Finish by smashing Extract root repeatedly and verify the values come out in sorted order, proving the heap-sort property.

In practice

When to use it — and what you give up

When it's the right tool

Priority queues — task schedulers, OS process scheduling, bandwidth management. You always want the highest-priority item next, and inserts/removes are frequent. A heap delivers both in O(log n).
Dijkstra's shortest-path algorithm — the min-heap sits at the core, serving up the next closest unvisited vertex in O(log V) per extraction.
Top-k problems — 'find the k largest numbers in a stream of millions.' Keep a min-heap of size k; if the new element beats the heap's minimum, swap it in. One pass, O(n log k), O(k) space.
Event-driven simulation — events are keyed by timestamp; the heap always serves the next event to process. Used in network simulators, game engines, and financial backtests.
Heapsort — build-heap in O(n), then extract-root n times: total O(n log n), in-place, no extra allocation. Not the fastest in practice (poor cache locality vs. quicksort) but optimal in theory.
Median-of-a-stream — maintain a max-heap of the lower half and a min-heap of the upper half; the median is always the tops of those two heaps.

When to reach for something else

Arbitrary lookups by key — a heap doesn't know where key k lives. Use a hash map (O(1) average) or BST (O(log n)) instead.
Sorted iteration over all elements — extracting n times is O(n log n) and destroys the heap. Just sort the array once with your language's built-in sort.
Decrease-key in Dijkstra at scale — the standard binary heap has no efficient decrease-key. A Fibonacci heap supports it in O(1) amortised, making Dijkstra O(E + V log V) instead of O((E + V) log V).
Ordered range queries — 'find everything between k₁ and k₂.' A balanced BST or sorted array with binary search handles this; a heap cannot.

Pros

O(1) peek — the min (or max) is always at index 0. No traversal, no comparison.
O(log n) insert and extract — bubble-up and sift-down each traverse at most one root-to-leaf path, which is at most ⌊log₂ n⌋ levels deep.
O(n) bulk construction — Floyd's bottom-up buildHeap is provably linear, beating O(n log n) repeated insertion when all values are known upfront.
Cache-friendly array layout — no pointer chasing. Parent and children of node i are at predictable offsets; prefetchers love it.
Dead simple implementation — three index formulas and two loops. No rotations, no colour bits, no rebalancing cases. The entire data structure fits in 40 lines of code.

Cons

O(n) arbitrary search — there is no ordering between siblings, so finding a node by value requires scanning the whole array. The heap property only constrains the vertical (parent–child) axis.
No decrease-key without augmentation — updating the priority of an existing element requires knowing its index (needs a separate map) and then bubbling up or down. Standard library heaps rarely expose this.
Poor cache performance during sift-down at scale — later levels of the tree (most of the nodes) map to high array indices that may span many cache lines, causing cache misses as the sift-down zigzags down.
Not stable — equal-priority elements may be extracted in any order. If insertion order matters, you must embed a sequence number in the key.
Not a search structure — if your workload is 'find, update, delete arbitrary keys,' a heap forces you to either scan (O(n)) or maintain a parallel index map. A balanced BST is the cleaner fit.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

BinaryHeap.ts

// Array-backed binary min-heap.
// Swap min → max comparator for a max-heap.
class BinaryHeap {
  private data: number[] = [];

  // Index helpers — the only "pointers" this structure needs.
  private parent(i: number): number { return Math.floor((i - 1) / 2); }
  private left(i: number):   number { return 2 * i + 1; }
  private right(i: number):  number { return 2 * i + 2; }

  private swap(a: number, b: number): void {
    [this.data[a], this.data[b]] = [this.data[b], this.data[a]];
  }

  // Min-heap property: parent ≤ children.
  private less(a: number, b: number): boolean {
    return this.data[a] < this.data[b];
  }

  // O(log n) — append then bubble up.
  push(value: number): void {
    this.data.push(value);
    this.bubbleUp(this.data.length - 1);
  }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const p = this.parent(i);
      if (this.less(i, p)) { this.swap(i, p); i = p; }
      else break;
    }
  }

  // O(1) — root is always index 0.
  peek(): number | undefined { return this.data[0]; }

  // O(log n) — remove root, promote last, sift down.
  pop(): number | undefined {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  private siftDown(i: number): void {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = this.left(i), r = this.right(i);
      if (l < n && this.less(l, smallest)) smallest = l;
      if (r < n && this.less(r, smallest)) smallest = r;
      if (smallest === i) break;
      this.swap(i, smallest);
      i = smallest;
    }
  }

  // O(n) — Floyd's bottom-up build; faster than n × push().
  static buildHeap(values: number[]): BinaryHeap {
    const h = new BinaryHeap();
    h.data = [...values];
    for (let i = Math.floor(h.data.length / 2) - 1; i >= 0; i--) {
      h.siftDown(i);           // sift every internal node, leaves skip
    }
    return h;
  }

  get size(): number { return this.data.length; }
}

References & further reading

7 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

In an array-backed binary heap, where are the left child, right child, and parent of node at index i?

question 02 / 03

Why is Floyd's bottom-up buildHeap O(n), even though it calls siftDown — an O(log n) operation — for every internal node?

question 03 / 03

You need to find whether a specific value k exists in a binary min-heap of n elements. What is the time complexity of the most straightforward correct approach?

0/3 answered