When to use. Repeatedly need the current min or max; streaming top-k; merge sorted streams.
Complexity. Time Insert/pop O(log n); peek O(1). Space O(n) for the heap.
Who gets asked. Top-k is intern/mid. Two-heap running median and custom comparators show up in senior screens.
Prereq. Trees (heap shape) and Big O.
Heaps
A binary heap is a tree stored in an array that keeps the min (or max) at the root. Interviews care about the priority-queue API, not drawing heapify by hand.
The idea
Insert and pop are O(log n). Peek is O(1). In JavaScript, use a small heap class or a sorted insertion only when n is tiny — there is no built-in heap. In Python, heapq is a min-heap; negate for max.
Top-k: keep a min-heap of size k of the best so far. Each new value either misses or replaces the root. Time O(n log k).
Two heaps split a stream into lower half (max-heap) and upper half (min-heap) for a running median. Senior follow-up, not intern homework.
Worked example
K largest values
Unsorted numbers and k. Return the k largest, any order. Example: [7, 2, 9, 4, 8], k = 3 → {7, 9, 8}.
Push the first k values into a min-heap.
For each remaining value, if it is larger than the root, pop and push.
The heap is the answer. Do not full-sort unless n is small and you say O(n log n).
class MinHeap {
constructor() { this.a = []; }
size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
this.a.push(x);
this._up(this.a.length - 1);
}
pop() {
const top = this.a[0];
const last = this.a.pop();
if (this.a.length) {
this.a[0] = last;
this._down(0);
}
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] <= this.a[i]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
_down(i) {
const n = this.a.length;
while (true) {
let s = i;
const l = i * 2 + 1;
const r = l + 1;
if (l < n && this.a[l] < this.a[s]) s = l;
if (r < n && this.a[r] < this.a[s]) s = r;
if (s === i) break;
[this.a[s], this.a[i]] = [this.a[i], this.a[s]];
i = s;
}
}
}
function kLargest(nums, k) {
const heap = new MinHeap();
for (const n of nums) {
heap.push(n);
if (heap.size() > k) heap.pop();
}
const out = [];
while (heap.size()) out.push(heap.pop());
return out;
}
Time O(n log k). Space O(k).
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Merge k sorted streams
k sorted lists. Produce one sorted sequence. You may not flatten and sort if that is O(N log N) and they want O(N log k).
Aim: O(N log k) time, O(k) heap space
Kth smallest so far
A stream of numbers. After each insert, answer the kth smallest (k fixed).
Aim: O(log n) per insert with a size-k heap or two-heap split
Task cooldown
Tasks with frequencies and a cooldown between two of the same kind. Minimum slots to finish all. Greedy with a max-heap of counts.