DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on • Originally published at github.com

I built a binary heap visualizer: bubble-up, sift-down, and O(n) heapify with the array and tree side by side

#algorithms #javascript #computerscience #datastructures

"Just use a priority queue" is common advice, and the priority queue is almost always a binary heap. It's a data structure that looks like a tree but lives in a flat array, and once that clicks, the O(log n) operations feel obvious. So I built one you can watch — insert, extract, and heapify, with the tree and the array shown at the same time.

▶ Live demo: https://dev48v.github.io/binary-heap/
Source: https://github.com/dev48v/binary-heap

The one rule

A binary heap is a complete binary tree (every level full, filled left to right) with a heap property: in a min-heap, every parent is ≤ both its children. That's it. The smallest element is therefore always at the root — O(1) to peek, which is the whole reason priority queues use it.

The array is the tree

Here's the trick that makes heaps so efficient: because the tree is always complete, you don't need nodes and pointers — you store it in a plain array in level order, and arithmetic gives you the tree:

parent(i)     = (i - 1) >> 1
leftChild(i)  = 2*i + 1
rightChild(i) = 2*i + 2
Enter fullscreen mode Exit fullscreen mode

The demo shows both views live, so you can see index [4] in the array light up as its node lights up in the tree.

insert — bubble up

Append to the end of the array (keeps it complete), then swap upward while you're smaller than your parent:

insert(v) {
  h.push(v);
  let i = h.length - 1;
  while (i > 0 && h[i] < h[(i-1)>>1]) {   // smaller than parent?
    swap(i, (i-1)>>1);
    i = (i-1)>>1;
  }
}
Enter fullscreen mode Exit fullscreen mode

The new value climbs at most the height of the tree — O(log n).

extract-min — sift down

The root is the answer, so return it. Move the last element to the root (to keep the tree complete), then sink it down, swapping with its smaller child until the rule holds:

extractMin() {
  const min = h[0];
  h[0] = h.pop();
  let i = 0;
  while (true) {
    let smallest = i, l = 2*i+1, r = 2*i+2;
    if (l < h.length && h[l] < h[smallest]) smallest = l;
    if (r < h.length && h[r] < h[smallest]) smallest = r;
    if (smallest === i) break;
    swap(i, smallest); i = smallest;
  }
  return min;
}
Enter fullscreen mode Exit fullscreen mode

Also O(log n). In the demo you watch the last element teleport to the top and then sink back down.

heapify — O(n), not O(n log n)

To turn a random array into a heap, you could insert each element (n × O(log n) = O(n log n)). But there's a better way: sift down from the last parent up to the root:

for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i);
Enter fullscreen mode Exit fullscreen mode

This is O(n) — a classic result that surprises people. The reason: most nodes are near the bottom and barely sift, and the sum of the work across all levels converges to a constant times n. The demo builds a heap this way with heapify random so you can watch it happen bottom-up.

Where you'll meet it

  • Dijkstra / Prim — pull the cheapest node/edge next.
  • Huffman coding — repeatedly merge the two smallest frequencies.
  • Heapsort — build a max-heap, then extract the max n times (in-place, O(n log n), no extra memory).
  • Top-k / streaming medians / event simulation — anything that needs "the best one next, cheaply."

Insert some values, extract the root, flip between min and max, and heapify a random array. If it made heaps click, a star helps others find it: https://github.com/dev48v/binary-heap

Top comments (0)