Heaps and top-K
A heap orders only each parent against its children, and that is enough to keep the smallest value at the front.
Predict first
Before you read: predict
ExamHall's proctor console shows the three most suspicious attempts of an exam while anti-cheat scores stream in. It keeps them in a min-heap with its library's helpers: push(h, x) adds x to the heap h, and down(h) moves the value at h[0] down to its place.
What is cutoff?
const scores = [62, 96, 40, 77, 85, 58, 91, 70];const top = [];for (const s of scores) { if (top.length < 3) push(top, s); else if (s > top[0]) { top[0] = s; down(top); }}export const cutoff = top[0];The 30-second version
A binary heap is an array in which every parent is no larger than its children, so the smallest value sits at index 0. Insert and remove-min each walk one path: O(log n). For the top K of n items keep a min-heap of K: its root is the cut-off a new item must beat. JavaScript has no built-in heap.
A heap orders only each parent against its children, and that is enough to keep the smallest value at the front.
How it works
Step 1 of 10
Analogy: A silk farm keeping the season's ten heaviest cocoons for breeding (sericulture)
| At the silk farm | In the code |
|---|---|
| the ten heaviest cocoons of the harvest go to the breeding box, and the lightest of the ten sits on the scale's tray as the weight to beat | a min-heap of K, its root the cut-off (step 6) |
| a heavier cocoon takes the tray, the old one goes to the reeling pan, and the keeper works out which of the ten is now lightest | replace the root, then sink (steps 4, 6) |
| the breeding box records which ten, not their order by weight | heap order, not rank order (step 8) |
| the keeper never holds the whole harvest at the scale | O(k) memory on a stream (step 7) |
In real terms: a heap answers one question fast, "which is the smallest?", and repairs that answer along one path after each change.
Breaks down when: the keeper can look over all ten to find the new lightest, while a heap finds it along one path, because each parent is kept no larger than its two children.
Contrasting case: weighing every cocoon of the season and ranking them all at the end. The same ten come out, but every cocoon is kept until then, and nothing is known before the last one.
Examples, run for real
4.1 ExamHall EXH-4920: the console re-sorted every score
ExamHall's proctor console showed each exam's ten most suspicious attempts by keeping every anti-cheat score and re-sorting the list as each one arrived. In a 2,000-candidate exam the panel fell behind the stream (EXH-4920). MR !5220 keeps a min-heap of ten per exam (step 6). On a seeded stream of 2,000 scores:
4.1 EXH-4920 the old panel kept all 2,000 scores and re-sorted after each one: at least n − 1 comparisons for n scores, 1,999,000 in all (arithmetic, not run)
4.1 MR !5220 a min-heap of ten: 2,238 comparisons between scores in all, never more than 10 scores held
4.1 MR !5220 the ten it holds are the ten highest of all 2,000 (checked against a full sort)Sorting n scores needs at least n − 1 comparisons whatever the algorithm, so re-sorting after every arrival grows with the square of the stream (the prerequisite's step 4). The heap holds ten scores, compares each new score with its root, and sinks the few that get in (steps 6, 7).
4.2 Streaming: the three most-played tracks of the hour
A music service's "trending now" box counts each track's plays in one pass with a Map, then keeps the three highest counts in a min-heap of [plays, track] pairs:
4.2 one pass over 57 plays: 9 tracks counted in a Map
4.2 the heap holds track-c (9), track-a (16), track-b (14); ranked at the end: track-a (16), track-b (14), track-c (9)The heap holds the right three, the smallest count at its root; it says nothing about the order of the other two, so the box sorts its three before showing them (steps 2, 8).
Try it
Answer first, then check. Nothing is saved.
Question 1 of 8
A chat app keeps its reminders in a min-heap by due minute. To hand out the next reminder it moves the last one to h[0] and calls down(h), which is complete apart from its loop body:
In what order does the loop body run them, top first?
export function down(h) { let i = 0; for (;;) { let c = 2 * i + 1; if (c >= h.length) return; /* the four lines, in order */ }}Your order
- 1empty
- 2empty
- 3empty
- 4empty
Tap the lines in the order you expect.
Question 2 of 8
A video app keeps the start seconds of the ad breaks still to play in a min-heap. Its helper parent(i) returns the index of the parent of index i. Six breaks are added in this order:
What is out?
function push(h, x) { h.push(x); let i = h.length - 1; while (i > 0) { const p = parent(i); if (h[p] <= h[i]) break; [h[p], h[i]] = [h[i], h[p]]; i = p; }}const breaks = [];for (const s of [50, 30, 80, 10, 90, 20]) push(breaks, s);export const out = breaks.join(' ');Question 3 of 8
ExamHall's grading queue keeps waiting essays in a min-heap by submission minute. Taking the earliest essay moves the last entry to the top and sinks it; the harness counts each comparison through less:
How many times does less run?
let compares = 0;const less = (a, b) => { compares++; return a < b; };function down(h) { let i = 0; for (;;) { let c = 2 * i + 1; if (c >= h.length) return; if (c + 1 < h.length && less(h[c + 1], h[c])) c++; if (!less(h[c], h[i])) return; [h[i], h[c]] = [h[c], h[i]]; i = c; }}const waiting = [1, 3, 2, 8, 4, 5, 6, 12, 10, 9, 11, 13, 14, 15, 7];waiting[0] = waiting.pop();down(waiting);export { compares };Question 4 of 8
A payments ledger's daily report lists the three largest refunds. A teammate's first version uses a max-heap helper pair: pushMax(h, x) adds x, and popMax(h) removes h[0], the largest value in h:
What is report?
export function largest(amounts, k) { const h = []; for (const a of amounts) { pushMax(h, a); if (h.length > k) popMax(h); } return h.sort((x, y) => y - x).join(' ');}export const report = largest([55, 91, 47, 78, 88, 62], 3);Question 5 of 8
the interviewer says: "Each exam room's proctor laptop sends its alerts as a list sorted by time, like [{ t: 3, id: 'r1-a' }, { t: 8, id: 'r1-b' }]. Write mergeAlerts(rooms): return every room's alerts in one list sorted by t. Alerts with the same t keep their rooms' order, room 0 first, and within a room their own order. Leave the rooms' lists as they are." You have 15 minutes and a plain editor.
Before you type: say your test list out loud.
Name at least six tests, each with its input and what it expects.
Question 6 of 8
the interviewer says: "Each exam room's proctor laptop sends its alerts as a list sorted by time, like [{ t: 3, id: 'r1-a' }, { t: 8, id: 'r1-b' }]. Write mergeAlerts(rooms): return every room's alerts in one list sorted by t. Alerts with the same t keep their rooms' order, room 0 first, and within a room their own order. Leave the rooms' lists as they are." You have 15 minutes and a plain editor.
Now write it, in 15 minutes, from a blank file that exports mergeAlerts.
Question 7 of 8
A charity auction keeps the five highest of 40 bids in a min-heap, written in the form a cheatsheet gives. push(h, x) adds x to the heap h; pop(h) removes and returns h[0]:
How many times does pop run for the 40 bids?
const bids = Array.from({ length: 40 }, (_, i) => 200 + ((i * 37) % 101));const h = [];for (const b of bids) { push(h, b); if (h.length > 5) pop(h);}export { h };Question 8 of 8
A chat app opens with seven conversations waiting for a reply, listed by the minute of each one's last unanswered message, and builds a min-heap from them in place, earliest minute first:
What is out?
function down(h, i) { for (;;) { let c = 2 * i + 1; if (c >= h.length) return; if (c + 1 < h.length && h[c + 1] < h[c]) c++; if (h[i] <= h[c]) return; [h[i], h[c]] = [h[c], h[i]]; i = c; }}const waits = [60, 15, 10, 40, 25, 35, 90];for (let i = Math.floor(waits.length / 2) - 1; i >= 0; i--) down(waits, i);export const out = waits.join(' ');Go deeper
Pro tips
- For top K, keep a min-heap of size K and drop the smallest; say O(n log k), and that it beats sorting when K is small. When: a question says "top", "largest" or "most frequent" K. (The curriculum row's tip, [SELF].) Verify (RAN,
tips.mjs):tip 1 a min-heap of 10 over 50,000 and 100,000 seeded scores: 50,445 and 100,476 comparisons (×1.99), never more than 10 held - Say what a tie at the cut-off does. When: scores, counts or times can repeat. With
>, a value equal to the root stays out and the earlier one keeps its place; with>=, the later one replaces it. Verify (RAN,tips.mjs):tip 2 top 2 of 5, 9, 7a, 7b: with > the heap keeps 7a 9 · with >= it keeps 7b 9
Source
Vendor pages change, so its claims are labelled as of 2026-10-17; every count this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.
- Tech Interview Handbook, Heap cheatsheet (the curriculum row's second source), https://www.techinterviewhandbook.org/algorithms/heap/ (
tih-heap.txt). As of 2026-10-17.- "A heap is a specialized tree-based data structure which is a complete tree that satisfies the heap property." (step 1)
- "Min heap - In a min heap, the value of a node must be smallest among the node values in its entire subtree." (step 2)
- "InsertO(log(n))" and "RemoveO(log(n))" (steps 3, 4; the page's table, cells run together in the saved text)
- "Find max/minO(1)" (step 5)
- "If you require the top k elements use a Min Heap of size k." (step 6)
- "Whenever the heap size exceeds k, remove the minimum element, that will guarantee that you have the k largest elements." (step 6)
- "Heapify (create a heap out of given array of elements)O(n)" (step 9)
- "JavaScriptN/A" (step 10; the page's table of library heaps)
- "If you see a top or lowest k being mentioned in the question, it is usually a signal that a heap can be used to solve the problem" (tip 1)
- Its essential questions include "Merge K Sorted Lists".
Related lessons
Checked against the tools and docs as of 2026-10-17.