Introduction

Suppose you have a pile of numbers and you keep asking the same question: what is the smallest one right now? New numbers arrive, the smallest gets taken away, and you ask again. Scan the whole pile every time and you pay for it. Keep the pile fully sorted and every insertion is expensive. There is a cheaper middle ground.

A binary heap is that middle ground. It is nothing more than an array that obeys one rule: every element is smaller than or equal to its two children, where the children of position i live at positions 2i+1 and 2i+2. That single rule — the heap property — means the smallest element is always sitting at the very front, at index 0. No search required.

The magic is that you can insert a new value or remove the smallest while keeping that promise, each in just O(log⁡n)O(\log n) steps. The binary heap was invented by J. W. J. Williams in 1964 as the engine for a sorting method called heapsort. It is one of the cleanest, most-solved ideas in computer science — and it hides inside a structure you already know.

Build a Heap

Below is a live min-heap shown two ways at once: as the underlying array and as the tree that array encodes. Type a number and press Insert — watch it climb (sift up) until no parent is larger. Press Extract min to pull the smallest off the front and watch the gap close (sift down).

<p class="hint">A <b>min-heap</b> is just an array where every parent is no larger than its children (child of <i>i</i> at <i>2i+1</i> and <i>2i+2</i>). Insert a number to watch it <b>sift up</b>; extract the minimum to watch the gap <b>sift down</b>. The smallest value is always at index 0.</p>
<div class="controls">
  <input id="val" type="number" value="42" />
  <button id="insert" type="button">Insert</button>
  <button id="extract" type="button">Extract min</button>
  <button id="rand" type="button" class="ghost">Random</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div class="status" id="status">Heap is empty. Insert a number.</div>
<div class="label">Tree view</div>
<div id="tree" class="tree"></div>
<div class="label">Array (index : value)</div>
<div id="array" class="array"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .4rem; }
input { font: 600 14px system-ui, sans-serif; width: 80px; padding: .4rem .5rem;
        border: 1px solid #adb1b8; border-radius: 8px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.3em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.label { font-size: .78rem; text-transform: uppercase; letter-spacing: .05em; color: #6b7785;
         margin: .7rem 0 .25rem; font-weight: 700; }
.tree { position: relative; height: 200px; border: 1px solid #e1e6eb; border-radius: 10px;
        background: #f7f9fb; overflow: hidden; }
.node { position: absolute; width: 38px; height: 38px; margin: -19px 0 0 -19px;
        display: flex; align-items: center; justify-content: center; border-radius: 50%;
        background: #1d3557; color: #fff; font: 700 14px ui-monospace, monospace;
        transition: left .25s, top .25s, background .25s; }
.node.root { background: #e63946; }
.edge { position: absolute; height: 2px; background: #c2cdd8; transform-origin: 0 0; }
.array { display: flex; flex-wrap: wrap; gap: 4px; }
.cell { min-width: 42px; padding: .35rem; border: 1px solid #cdd9e3; border-radius: 7px;
        background: #e8eef3; text-align: center; font: 700 14px ui-monospace, monospace; color: #1d3557; }
.cell .idx { display: block; font-size: 10px; color: #6b7785; font-weight: 600; }
.cell.first { background: #e63946; color: #fff; border-color: #c92f3c; }
.cell.first .idx { color: #ffd9dd; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A binary min-heap stored as a flat array `h`. Parent of i = (i-1>>1);
// children = 2i+1, 2i+2. Invariant: h[parent] <= h[child] everywhere.
// insert(): append, then sift up. extractMin(): take h[0], move last to front,
// sift down. Both touch one leaf<->root path => O(log n).
const h = [];

function swap(i, j){ const t = h[i]; h[i] = h[j]; h[j] = t; }

function siftUp(i){
  while (i > 0){
    const p = (i - 1) >> 1;
    if (h[p] <= h[i]) break;
    swap(i, p); i = p;
  }
}
function siftDown(i){
  const n = h.length;
  while (true){
    let s = i, l = 2*i+1, r = 2*i+2;
    if (l < n && h[l] < h[s]) s = l;
    if (r < n && h[r] < h[s]) s = r;
    if (s === i) break;
    swap(i, s); i = s;
  }
}
function insert(v){ h.push(v); siftUp(h.length - 1); }
function extractMin(){
  if (h.length === 0) return null;
  const min = h[0];
  const last = h.pop();
  if (h.length > 0){ h[0] = last; siftDown(0); }
  return min;
}

function setStatus(t, ok){ const s = document.getElementById('status');
  s.textContent = t; s.className = 'status' + (ok ? ' ok' : ''); }

function render(){
  // Array view
  const a = document.getElementById('array'); a.innerHTML = '';
  if (h.length === 0){ a.innerHTML = '<span style="color:#6b7785;font-size:.9rem">(empty)</span>'; }
  h.forEach((v, i) => {
    const c = document.createElement('div');
    c.className = 'cell' + (i === 0 ? ' first' : '');
    c.innerHTML = '<span class="idx">' + i + '</span>' + v;
    a.appendChild(c);
  });
  // Tree view: place node i at depth = floor(log2(i+1)), spread across its level.
  const tree = document.getElementById('tree'); tree.innerHTML = '';
  const W = tree.clientWidth || 520, levelH = 48, topPad = 24;
  const pos = (i) => {
    const depth = Math.floor(Math.log2(i + 1));
    const first = (1 << depth) - 1;          // first index on this level
    const slot = i - first;                  // position within level
    const count = 1 << depth;                // nodes on a full level
    const x = W * (slot + 0.5) / count;
    const y = topPad + depth * levelH;
    return { x, y };
  };
  // edges first
  for (let i = 1; i < h.length; i++){
    const p = (i - 1) >> 1;
    const a1 = pos(p), b1 = pos(i);
    const dx = b1.x - a1.x, dy = b1.y - a1.y;
    const len = Math.sqrt(dx*dx + dy*dy);
    const ang = Math.atan2(dy, dx) * 180 / Math.PI;
    const e = document.createElement('div'); e.className = 'edge';
    e.style.left = a1.x + 'px'; e.style.top = a1.y + 'px';
    e.style.width = len + 'px'; e.style.transform = 'rotate(' + ang + 'deg)';
    tree.appendChild(e);
  }
  // nodes
  h.forEach((v, i) => {
    const p = pos(i);
    const n = document.createElement('div');
    n.className = 'node' + (i === 0 ? ' root' : '');
    n.style.left = p.x + 'px'; n.style.top = p.y + 'px';
    n.textContent = v;
    tree.appendChild(n);
  });
}

document.getElementById('insert').addEventListener('click', () => {
  const raw = document.getElementById('val').value;
  const v = parseInt(raw, 10);
  if (Number.isNaN(v)){ setStatus('Type a whole number first.', false); return; }
  insert(v); render();
  setStatus(fmt('Inserted %v%. Smallest is now %v2% (index 0).', { v: v, v2: h[0] }), true);
});
document.getElementById('extract').addEventListener('click', () => {
  if (h.length === 0){ setStatus('Heap is empty — nothing to extract.', false); return; }
  const m = extractMin(); render();
  setStatus(fmt('Extracted minimum %m%.%v%', { m: m, v: h.length ? ' New smallest: ' + h[0] + '.' : ' Heap is now empty.' }), true);
});
document.getElementById('rand').addEventListener('click', () => {
  const v = Math.floor(Math.random() * 99) + 1;
  document.getElementById('val').value = v;
  insert(v); render();
  setStatus(fmt('Inserted random %v%. Smallest is now %v2%.', { v: v, v2: h[0] }), true);
});
document.getElementById('reset').addEventListener('click', () => {
  h.length = 0; render(); setStatus('Heap cleared. Insert a number.', false);
});

// Seed a small heap so the view is not empty on load.
[42, 17, 63, 8, 25, 50].forEach(insert);
render();
setStatus(fmt('Seeded heap. Smallest is %v% at index 0.', { v: h[0] }), true);
Result
Console

Notice the discipline. The heap is never fully sorted, yet the smallest element is always at index 0. Each insert or extract only touches one path from a leaf to the root — about log⁡2\log_{2} n swaps — so even with a million elements that is only twenty steps. Keep pressing Extract min and the numbers come out in perfect sorted order: that is exactly how heapsort works.

The Real Complexity

Heaps are a solved problem: the costs are known exactly and proven optimal for what they do.

  • Peek (find-min): O(1)O(1). The smallest element is always at index 0 — just read it.
  • Insert: O(log⁡n)O(\log n). Append at the end, then sift up. The element rises at most the height of the tree, which is ⌊log⁡2\log_{2} n⌋.
  • Extract-min: O(log⁡n)O(\log n). Move the last element to the front, then sift down along one root-to-leaf path.
  • Build-heap: O(n)O(n). Heapifying n arbitrary values bottom-up is linear, not n log n — a famously tidy result, because most nodes are near the bottom and sift down only a little.
  • Heapsort: O(nlog⁡n)O(n \log n), in place. Build the heap, then extract the minimum n times. The bound holds in the worst case, with no extra memory.

There is no asymptotic trick hiding here and nothing open to discover — a comparison-based priority queue cannot beat O(log⁡n)O(\log n) per update in general, and the heap meets that limit with a tiny, pointer-free array. Compare that to the Traveling Salesman problem, where no fast algorithm is known: heaps sit firmly on the easy side of computation.

Where It Matters

"Always give me the most urgent item next" is everywhere, and the heap is the standard answer:

  • Shortest paths: Dijkstra's algorithm and A* repeatedly pull the closest unvisited node from a priority queue — a heap makes that the dominant, efficient step.
  • Schedulers and simulations: operating systems and discrete-event simulators keep tasks or events in a heap ordered by deadline or timestamp.
  • Streaming top-k: to track the k largest items in a torrent of data, keep a heap of size k and let small ones fall off.
  • Huffman coding: building an optimal compression tree repeatedly merges the two least-frequent symbols — straight from a min-heap.

Wherever you see a shortest-path search or a "process the next deadline" loop, there is almost certainly a heap underneath. Master this one little array rule and a whole family of algorithms suddenly runs fast.

Conclusion

The binary heap is a small idea with an enormous reach: one rule — every parent no larger than its children — laid over an ordinary array, and suddenly you have a priority queue that answers "what's smallest?" instantly and updates in logarithmic time, with no pointers and no wasted memory.

It has been fully understood since 1964, its costs are provably optimal, and yet it still quietly powers shortest-path search, schedulers, compressors and simulations every second of every day. Not every problem is as hard as P vs NP. Some of the most useful ones, like the heap, were elegantly solved long ago — and they are well worth knowing by heart.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/heaps/Content licensed under CC BY-NC 4.0.