Min-Heap Operations: The Data Structure Behind Every Priority Queue

Every "find the kth largest", "merge k sorted lists", "process the cheapest option first" problem hides the same question underneath: how do you repeatedly grab the minimum of a changing collection without re-sorting it every time? The min-heap is the answer, and it's one of the few data structures interviewers expect you to build from scratch, not just import.

The whole structure rests on one deliberately weak promise: every parent is less than or equal to its children. Not sorted — just locally ordered. That single relaxation turns O(n) operations into O(log n) ones.

Two operations do all the work: insert (append, then bubble the new value up) and extract-min (take the root, then sift the replacement down). Master those two loops and you've mastered heaps.

The problem#

Design a structure that supports three operations on a collection of numbers:

• insert(value) — add a number
• extractMin() — remove and return the smallest number
• peek() — read the smallest number without removing it

The operations interleave arbitrarily — and that interleaving is the hard part, because a one-time sort doesn't survive it.

This is exactly what a priority queue is: Dijkstra's algorithm extracting the closest unvisited node, a scheduler running the most urgent task, a k-way merge picking the smallest head. The min-heap is the standard implementation.

The brute force baseline#

Without a heap you have two naive layouts, and each one is fast at exactly half the job:

A sorted array flips the trade: extract-min is O(1) (pop the front), but every insert has to find its slot and shift everything after it — O(n).

Either way, one of the two operations costs O(n), so a workload of n mixed operations degrades to O(n²). Run Dijkstra on a 10⁵-node graph with an unsorted-array queue and you're doing ten billion comparisons on extracts alone. The heap's pitch: make both operations O(log n) by refusing to keep the collection fully sorted.

The key insight: a complete tree, flat in an array#

A min-heap is a complete binary tree — every level full except possibly the last, which fills left to right — with one rule, the heap property: parent <= children, everywhere.

Two consequences fall out immediately:

• The minimum is always at the root. Follow the property upward from any node and values only shrink.
• The property says nothing about siblings or cousins. [1, 3, 8, 5] is a valid min-heap even though it isn't sorted — 3 and 8 are siblings, and their order relative to each other is irrelevant.

Completeness is what makes the tree storable in a plain array with zero pointers. Read the tree level by level and the index math is fixed:

Appending to the array is exactly "add a node at the next free slot of the bottom level", and popping the last element is exactly "remove the bottom-rightmost node" — so the shape stays complete for free.

The payoff: a complete tree with n nodes is only ⌊log₂ n⌋ levels deep, and fixing a heap violation only ever walks one root-to-leaf path. That path is the entire cost of both operations.

The optimal solution#

This is the algorithm the visualizer animates step by step — same approach, same variable names:

Why each piece is the way it is:

• Insert appends first, fixes second. Appending anywhere else would break completeness. The only node possibly out of place is the new one, and only relative to its ancestors — so bubble-up compares against parent(i) alone and climbs.
• Extract-min replaces the root with the last element. You must remove the root's value, but you must delete the bottom-right slot to stay complete. Moving the last element into the root does both at once, at the cost of one (probably misplaced) value at the top — which sift-down repairs.
• Sift-down swaps with the smaller child. After the swap, that child becomes the parent of the other child. Only the smaller of the two can legally sit above both.
• The if (heap.length > 0) guard matters: on a single-element heap, heap.pop() already removed the root itself, and writing it back would resurrect a deleted value.

Walkthrough: insert 5, 3, 8, 1 — then extract-min#

Step 4 is bubble-up at full stretch: 1 enters at index 3 and climbs the path 3 → 1 → 0 in two swaps, never touching 8 in the other subtree. Step 6 shows the smaller-child rule: the root's children are 3 and 8, and swapping with 8 would have put 8 above 3 — a brand-new violation. Note the final array [3, 5, 8] happens to be sorted; [1, 3, 8, 5] in step 4 wasn't. Both are valid heaps — the property never promised sorted.

Complexity#

Both heap loops move strictly one level per iteration — up for insert, down for extract — and a complete tree has ⌊log₂ n⌋ levels, so neither loop can run more than ~17 times even at n = 10⁵. Space is O(n) for the array itself; both operations work in place.

One more number worth quoting in interviews: building a heap from n existing values by repeated insert costs O(n log n), but a bottom-up heapify (sift-down from the last internal node to the root) does it in O(n), because most nodes sit near the leaves and sift almost nowhere.

Common mistakes#

• Treating the heap array as sorted. Only the root is guaranteed. Iterating heap in index order does not yield ascending values — to consume in order you must extract repeatedly.
• Sifting down toward the larger child. The swap must target the smaller child, or you place the larger child above its sibling and manufacture a new violation.
• Skipping the singleton guard in extract-min. When the heap has one element, heap.pop() removes the root itself; assigning heap[0] = last afterward re-inserts the value you just extracted.
• Mixing index conventions. parent = (i - 1) >> 1, children 2i + 1 / 2i + 2 are the 0-indexed formulas. The classic textbook i/2, 2i, 2i + 1 are 1-indexed — combine the two and everything silently misparents.
• Wrong comparison strictness. Bubble-up continues only while heap[i] < heap[parent(i)] (strict), and sift-down stops on heap[i] <= heap[smallest]. Loosen either and duplicate values trigger pointless swaps — the visualizer's all-equal test case 4,4,4,4 finishes with zero swaps precisely because of this.
• Faking a priority queue with sort() in a loop. Re-sorting on every insert costs O(n log n) per operation. JavaScript has no built-in heap, so in an interview you write these ~25 lines.

Where this pattern shows up next#

Nearly every heap interview problem is these two operations plus one idea on top:

• Kth Largest Element in an Array — keep a min-heap capped at size k; the root becomes the answer.
• Top K Frequent Elements — hash-map counts feeding that same size-k heap.
• Last Stone Weight — a max-heap simulation that is pure insert/extract, the cleanest first application.
• Find Median from Data Stream — two heaps balanced against each other, the pattern's final boss.

Before those, step through it interactively — the visualizer renders the tree and the array side by side, so you can watch a bubble-up swap happen in both views at once.

FAQ#

Is a min-heap the same as a sorted array?#

No. A min-heap only guarantees that each parent is less than or equal to its children, which pins the minimum at index 0 and promises nothing else — [1, 3, 8, 5] is a perfectly valid min-heap. That weaker guarantee is the entire point: keeping a full sort costs O(n) per insert, while maintaining the heap property costs O(log n), because any violation can be repaired along a single root-to-leaf path.

Why are insert and extract-min O(log n)?#

Both operations create at most one heap violation and then chase it one level per swap: insert bubbles the appended value up toward the root, extract-min sifts the replacement root down toward the leaves. A complete binary tree with n nodes has ⌊log₂ n⌋ levels, so neither loop can exceed that many iterations — about 17 swaps for 100,000 elements.

How do I turn min-heap code into a max-heap?#

Flip the two comparisons: bubble up while the child is greater than its parent, and sift down toward the larger child, stopping when the parent is greater than or equal to it. Alternatively, keep the min-heap code untouched and negate values on the way in and out — the standard trick in languages like Python whose built-in heap is min-only.

Why does extract-min move the last element to the root instead of promoting a child?#

Because the tree must stay complete, and the only node that can disappear without leaving a hole is the bottom-rightmost one — the array's last element. Repeatedly promoting the smaller child would bubble a gap down to some arbitrary leaf position and break the shape, which in turn breaks the 2i + 1 / 2i + 2 index math. Moving the last element up and sifting it down fixes order while preserving shape.

Does JavaScript have a built-in priority queue?#

No — unlike Python's heapq or Java's PriorityQueue, JavaScript ships no heap, which is why interviewers ask you to implement one. An array plus the insert and extract-min functions shown here is a complete working priority queue in roughly 25 lines.