Heap
A heap is a nearly complete binary tree stored in an array that maintains a single invariant: a parent is always less than or equal to its children (min-heap) or greater than or equal to them (max-heap). This keeps the smallest/largest element at the top — read in O(1) — while push and pop cost only O(log n) because an element moves only along the height of the tree.
Don't confuse it with a priority queue: a priority queue is an abstract data type — it only promises "give me the highest-priority element" and says nothing about how it is built. A heap is the data structure that implements that promise, and it is the most common way to do so. Saying it the other way round — calling a heap "a kind of priority queue" — mixes up interface and implementation, a spot interviewers like to probe.
An important caveat: a heap does NOT fully sort anything — it only guarantees the parent–child relationship. Iterating the underlying array will not give ascending order.
JavaScript has no built-in heap (unlike Python's heapq or Java's PriorityQueue), so in an interview you need to build one on an array: the parent at index i, the two children at 2i+1 and 2i+2; push "floats up" (sift up) and pop "sinks down" (sift down).
Like a hospital emergency room — the most critical patient is always called first, regardless of who arrived first.
The waiting list does not need to be fully sorted; you only need to know exactly who is at the front, and to update that quickly when someone new arrives or the front person is called in.
How to spot it
When you see these cues in the problem, reach for Heap
| Keyword in the problem | Why it points to this topic |
|---|---|
| top K elements | Keep a size-K heap instead of sorting everything |
| K-th largest / smallest | Min-heap of exactly K elements, top is the answer |
| repeatedly extract max/min from a stream | O(log n) push/pop — no re-sorting each time |
| merge K sorted lists | A K-element heap always yields the next smallest |
| running median | Two heaps: max-heap lower half, min-heap upper half |
When to use
4 typical situations where this topic applies
You need the min/max MANY times while the data keeps changing (elements added/removed)
"Top k" problems — the k largest / smallest / most frequent elements
Merging k sorted sources (merge k sorted lists)
Maintaining a median or rank statistics over a continuous data stream
Priority scheduling: task scheduler, Dijkstra picking the nearest vertex
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
You only need the max/min once on static data → an O(n) scan is enough, building a heap is wasted work
You need to access an arbitrary element by rank (the i-th element) → sort once in O(n log n) and index into it
You need to check whether a specific value exists → a hash map gives O(1), a heap must scan in O(n)
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function heapPattern(nums: number[], k: number): R {
const heap = new MinHeap() // not built into JS — implement or emulate
for (const x of nums) {
heap.push(x)
// Keep exactly k elements → heap top is the k-th largest
if (heap.size() > k) heap.pop()
}
return heap.peek()
}Recap
A quick summary — reread it before your interview
Key points
A heap is stored in an array: parent at i, children at 2i+1 and 2i+2 — no pointers needed
Only the top of the heap is guaranteed to be the min/max; the rest is NOT fully sorted
"Top k" pattern: a min-heap of size k holding the k largest elements → O(n log k) instead of sorting in O(n log n)
Two heaps (a max-heap for the lower half + a min-heap for the upper half) maintain the median of a data stream in O(log n) per operation
Common mistakes
Thinking a heap is a fully sorted array — iterating the array inside a heap does not give ascending order
Forgetting that JavaScript has no built-in heap — practice implementing sift up/sift down before the interview
Looking for the k LARGEST elements but using a max-heap of size k (it should be a min-heap, so you can evict the smallest element when the size exceeds k)
Forgetting to check for an empty heap before pop/peek → undefined
Complexity
push/pop O(log n), peek O(1)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence