When you need to repeatedly fetch the current min or max from a changing collection, a binary heap gives O(log n) push/pop and O(1) peek — turning brute-force re-sorting into a tight incremental update.
A heap is a “give me the best one NOW” gadget that stays only partially sorted — so you pay O(log n) to order the single element you actually need, instead of O(n log n) to order all of them. The moment a problem says “repeatedly take the smallest / largest from a changing pile,” you want a heap.
Picture a tournament tree where every parent beat its two children. The overall champion sits at the top — that's the root, and reading it is free (O(1)). But the rest of the bracket is deliberately not fully ranked: you know each parent beats its kids, and nothing more. A full sort would rank all n players; a heap only ever cares about who's on top right now.
When you remove the champion or add a newcomer, you don't re-run the whole tournament — you just replay one path up or down the tree. That path islog n long, so each update is cheap. The genius is the storage: the tree is faked inside a flat array, no pointers at all.
The single most clarifying picture in heaps: the “tree” has no nodes and no pointers. It's an ordinary array, and the parent/child links are just arithmetic on indices:
Min-heap as a tree Same heap as a flat array
(smallest wins, sits on top) (children of i live at 2i+1, 2i+2)
2 idx : 0 1 2 3 4 5
/ \ val : [ 2 ][ 5 ][ 4 ][ 9 ][ 7 ][ 8 ]
5 4 | \___ \
/ \ / | \ \
9 7 8 parent 0 ──► kids 1,2
parent 1 ──► kids 3,4
parent 2 ──► kid 5
No left/right pointers. The array IS the tree: child(i)=2i+1 / 2i+2,
parent(i)=(i-1)/2. The root (idx 0) is the min — peek is O(1).Now watch a push. You append at the end and bubble up, swapping with the parent while you're smaller. Only the nodes on one root-to-leaf path ever move:
push(1) into [ 2 ][ 5 ][ 4 ][ 9 ][ 7 ][ 8 ]
append at the end, then BUBBLE UP while smaller than parent:
[..][ 1 ] ◄ new leaf (idx 6), parent is idx 2 = 4
swap with 4 ─► 1 rises
swap with 2 ─► 1 rises to the root
one swap PER LEVEL → at most log n swaps, never a full re-sort.
The rest of the array (the other ~n elements) is never inspected.O(n) per query for what a heap does in O(log n).When a problem smells like “extremes,” climb these rungs in order. The right heap shape falls out at the bottom:
O(N log k).The Top-K trick feels backwards until you see it run. To keep the k largest, hold a min-heap capped at size k. Its root is the smallest of your current winners — exactly the one to kick out when something bigger arrives:
Keep the 3 LARGEST. Heap = a MIN-heap capped at size 3.
The root is the SMALLEST of the current top-3 → the eviction door.
stream → 5 1 8 2 9 3
─────────────────────────────────────────────
push 5 [5]
push 1 [1 5]
push 8 [1 5 8]
push 2 [1 5 8] +2 → [1 2 5 8], size>3 → pop root(1) → [2 5 8]
push 9 [2 5 8] +9 → pop root(2) → [5 8 9]
push 3 3 < root(5) → evicted instantly, push+pop → [5 8 9]
─────────────────────────────────────────────
root = 5 = the 3rd largest. top-3 = {5,8,9}. cost O(n log k).The heap never holds more than k items, so every push/pop is O(log k), and the whole stream costs O(n log k) — far below a full O(n log n) sort when k ≪ n. And it works on a stream: you never need all the data at once.
“Find the median from a data stream” looks impossible without re-sorting after every insert — until you split the numbers into a low half and a high half and keep each in its own heap, oriented so both medians-in-waiting sit at the roots:
LOWER half UPPER half
(a MAX-heap) (a MIN-heap)
biggest-low at root smallest-high at root
\ /
... 3 1 2 [ 4 ] [ 6 ] 8 9 ...
▲ ▲
└── the median seam ──┘
odd count → median = root of the bigger heap
even count → median = average of the two facing roots
invariant → every low ≤ every high, and |sizes| differ by ≤ 1.The max-heap's root is the biggest of the low half; the min-heap's root is the smallest of the high half. Keep the two sizes within 1 of each other and the median is always one root (odd count) or the average of both roots (even count) — answered in O(1), with each insert only O(log n).
The number-one heap bug is getting the polarity backwards. Defuse it by stating the invariant in plain English first, then letting the code mirror it:
MIN-heap of size k; the root is the smallest survivor, so it's the first to go, and peek()is the kth largest.”lower first, then rebalance.# The size-k heap, said in words:
for each element x in the stream:
push x onto the heap # heap polarity is OPPOSITE the goal
if heap.size() > k: # one element too many?
heap.pop() # evict the root = loser of the top-k
# afterwards:
# heap holds the k winners
# heap.peek() (the root) = the kth best — the boundary elementHeaps are seductive, but they only pay off when you repeatedly pull extremes from a changing set. Several lookalikes have strictly better tools:
O(n log n) with no bookkeeping.O(n) average, beating the heap's O(n log k).O(n), no heap needed.i at 2i+1/2i+2); inserts sift up and pops sift down in O(log n), so the min/max is always at the root. The Visualize tab bubbles each insert up the tree.A binary heap is a complete binary tree stored in an array. It maintains one invariant: the root is always the minimum (min-heap) or maximum (max-heap). That lets you peek at the extreme in O(1) and push or pop in O(log n).
The key contrast with sorting: sorting the whole array costs O(n log n) regardless. A heap only does work proportional to the number of insertions and extractions you actually perform.
MinHeap / MaxHeap helper and implement it if asked, or state the assumption and proceed.For a one-shot kth-largest on a static array, quickselect gives O(n) average with O(1) extra space — often the optimal interview answer when there is no streaming constraint.
peek() — O(1): just read the root.push(v) — O(log n): append + bubble up.pop() — O(log n): swap root with last, remove, sift down.i lives at 2i+1 / 2i+2.Reach for a heap whenever the problem asks you to repeatedly extract an extreme value from a set that keeps changing, especially when the word "k" appears or data arrives as a stream.
| "k largest / k smallest / k most frequent" | size-k heap of the OPPOSITE extreme (min-heap for k largest) |
| "merge k sorted lists / arrays" | heap of list heads, pop min and push that list's next element |
| "running median / median of a stream" | two heaps: max-heap lower half + min-heap upper half |
| "schedule by priority / most frequent task first" | max-heap greedy — always process the highest-frequency / highest-priority item |
| "repeatedly take the smallest / largest from a pool" | heap — each extraction is O(log n) instead of O(n) linear scan |
| "kth largest in a stream" (online, elements arrive one by one) | min-heap of size k — peek() is always the kth largest seen so far |
| "shortest path in a weighted graph" (Dijkstra) | min-heap on (distance, node) — always relax the closest unvisited node next |
O(n log n) with a one-liner, no heap bookkeeping needed.O(n) with O(1) space — a heap is overkill.O(n) average vs. the heap's O(n log k). Mention it as the optimal alternative when there is no streaming requirement.SortedList equivalent) is the cleaner tool.When → Find the k largest (or k smallest) elements, either from a static array or a stream. Use a min-heap of size k so the root is always the weakest member of the current top-k — the first candidate to evict.
// Top-K Largest — keep a MIN-heap of size k.
// The heap always holds the k largest seen so far;
// the root (minimum of those k) is our "eviction candidate."
function topKLargest(nums: number[], k: number): number[] {
const heap = new MinHeap(); // min-heap (smallest at root)
for (const n of nums) {
heap.push(n);
if (heap.size() > k) heap.pop(); // evict the smallest of the top-k
}
// heap now contains the k largest; root = kth largest
return heap.toArray();
}When → You have k sorted lists (or iterators) and need one merged sorted output. Seed the heap with the first element of each list; each pop advances exactly that list.
// Merge K Sorted Lists — heap of heads, comparator on value.
interface HeapNode { val: number; listIdx: number; elemIdx: number; }
function mergeKSorted(lists: number[][]): number[] {
// min-heap ordered by val
const heap = new MinHeap<HeapNode>((a, b) => a.val - b.val);
for (let i = 0; i < lists.length; i++) {
if (lists[i].length > 0) heap.push({ val: lists[i][0], listIdx: i, elemIdx: 0 });
}
const result: number[] = [];
while (heap.size() > 0) {
const { val, listIdx, elemIdx } = heap.pop();
result.push(val);
const next = elemIdx + 1;
if (next < lists[listIdx].length) {
heap.push({ val: lists[listIdx][next], listIdx, elemIdx: next });
}
}
return result;
// Time O(N log k) — N total elements, k-entry heap per operation.
}O(N log N)when k ≪ N.When → Numbers arrive one at a time and you must answer findMedian() after each insertion. A max-heap holds the lower half, a min-heap the upper half; the median lives at one or both roots.
// Running Median — max-heap (lower half) + min-heap (upper half).
// Invariant: |lower.size - upper.size| <= 1, lower.peek() <= upper.peek().
class MedianFinder {
private lower = new MaxHeap(); // larger values in lower half
private upper = new MinHeap(); // smaller values in upper half
addNum(n: number): void {
// 1. Route: always push to lower first, then re-check boundary.
if (this.lower.size() === 0 || n <= this.lower.peek()) {
this.lower.push(n);
} else {
this.upper.push(n);
}
// 2. Rebalance: sizes may differ by at most 1.
if (this.lower.size() > this.upper.size() + 1) {
this.upper.push(this.lower.pop());
} else if (this.upper.size() > this.lower.size()) {
this.lower.push(this.upper.pop());
}
}
findMedian(): number {
if (this.lower.size() > this.upper.size()) return this.lower.peek();
return (this.lower.peek() + this.upper.peek()) / 2;
}
}lower.peek() <= upper.peek() is maintained by always routing through lower first and then re-checking the boundary element.When → The frequencies of n elements are bounded by n, so you can bucket-sort by frequency instead of heap-sorting. This upgrades Top-K Frequent from O(n log k) to O(n).
// Top-K Frequent Elements.
// Approach A — size-k min-heap by frequency: O(n log k).
// Approach B — bucket sort by frequency: O(n) — often preferred in interviews.
function topKFrequentBucket(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
// Bucket index = frequency (max frequency <= nums.length).
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, f] of freq) buckets[f].push(num);
const result: number[] = [];
for (let f = buckets.length - 1; f >= 0 && result.length < k; f--) {
result.push(...buckets[f]);
}
return result.slice(0, k);
}To find the k largest, use a min-heap (so the root — the weakest member — is what you evict when size exceeds k). Using a max-heap here keeps the k smallest instead. Burn in the mnemonic: "opposite extreme for Top-K."
When rolling a heap with a comparator, (a, b) => a - b gives a min-heap (a < b means a should be higher, so negative = a wins). Reversing to (a, b) => b - a gives a max-heap. Using the wrong sign silently inverts the heap, and bugs only surface at the boundary conditions.
The invariant requires that sizes differ by at most 1after every insertion, and that the lower max-heap's root is always <= the upper min-heap's root. A common mistake is forgetting to re-check the boundary after routing: push to lower first, then if lower.peek() > upper.peek() move the root across before rebalancing sizes.
Push and pop are O(log n), not O(1). For a problem doing n insertions into a size-k heap the total cost is O(n log k), not O(n). This matters when comparing against bucket sort (O(n)) or quickselect (O(n) average) — heap is not always the fastest option.