Heaps

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)$ 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.

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">{{hint}}</p>
<div class="controls">
  <input id="val" type="number" value="42" />
  <button id="insert" type="button">{{btn_insert}}</button>
  <button id="extract" type="button">{{btn_extract}}</button>
  <button id="rand" type="button" class="ghost">{{btn_random}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="status" id="status">{{status_empty}}</div>
<div class="label">{{label_tree}}</div>
<div id="tree" class="tree"></div>
<div class="label">{{label_array}}</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; }

// Code not found

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}$ 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.

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

• Peek (find-min): $O(1)$. The smallest element is always at index 0 — just read it.
• Insert: $O(\log n)$. Append at the end, then sift up. The element rises at most the height of the tree, which is ⌊$\log_{2}$ n⌋.
• Extract-min: $O(\log n)$. Move the last element to the front, then sift down along one root-to-leaf path.
• Build-heap: $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(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)$ 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.

"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.

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.