What is a heap?Core idea
A binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) where every parent is ≤ its children (min-heap) or ≥ them (max-heap). So the root is always the smallest (or largest) value.
Core operationsHow it works
| Operation | What it does | Cost |
|---|---|---|
| peek() | Return the root | O(1) |
| push(x) | Add at the end, then “sift up” while smaller than the parent | O(log n) |
| pop() | Remove the root, move the last element to the top, then “sift down” | O(log n) |
| heapify(array) | Build a heap from unsorted data | O(n) |
class MinHeap<T> {
private data: T[] = [];
constructor(private cmp: (a: T, b: T) => number) {}
get size() { return this.data.length; }
peek(): T | undefined { return this.data[0]; }
push(v: T) {
this.data.push(v);
let i = this.data.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.cmp(this.data[i], this.data[parent]) >= 0) break;
[this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
i = parent;
}
}
pop(): T | undefined {
if (this.data.length === 0) return undefined;
const top = this.data[0];
const last = this.data.pop()!;
if (this.data.length) {
this.data[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < this.data.length && this.cmp(this.data[l], this.data[smallest]) < 0) smallest = l;
if (r < this.data.length && this.cmp(this.data[r], this.data[smallest]) < 0) smallest = r;
if (smallest === i) break;
[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
i = smallest;
}
}
return top;
}
}The Top K patternPattern
Top K problems ask for the K largest, smallest or most frequent elements. Keep a heap of size K, so memory stays O(K) instead of O(n).
function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
// [freq, num], smallest frequency on top
const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
for (const [num, freq] of counts) {
heap.push([freq, num]);
if (heap.size > k) heap.pop(); // evict the least frequent
}
const result: number[] = [];
while (heap.size) result.push(heap.pop()![1]);
return result;
}Merging K sorted listsPattern
Put the head of each list in a min-heap. Repeatedly pop the smallest node, attach it to the result, and push that node's next. With N nodes in total, this is O(N log K).
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
for (const l of lists) if (l) heap.push(l);
const dummy = new ListNode(0);
let tail = dummy;
while (heap.size) {
const node = heap.pop()!;
tail.next = node;
tail = node;
if (node.next) heap.push(node.next);
}
return dummy.next;
}Median of a stream (two heaps)Pattern
Keep a max-heap for the lower half of the numbers and a min-heap for the upper half. After each insert, rebalance so their sizes differ by at most one. The median is the top of the bigger heap, or the average of both tops.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph LR
L["max-heap: lower half<br/>1 · 3 · 5 (top = 5)"] --- M(("median"))
M --- U["min-heap: upper half<br/>7 · 9 · 12 (top = 7)"]
class L blue
class U orange
class M green
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eWhen to use a heapWhen to use
Common mistakesPitfalls
In the interviewIn the interview
In most languages you can use the built-in priority queue. Ask first, rather than writing a heap from scratch.
Frequently asked questionsFAQ
Is a priority queue the same as a heap?
In interviews, treat them as the same thing: practically every standard library implements a priority queue as a binary heap sitting behind a comparator. Saying use a min-heap or use a priority queue means the same operation to an interviewer, so pick whichever phrasing matches your language and move on.
What is the difference between heapify and repeated inserts?
Heapify builds the heap once from a full array in O(n) by sifting each parent down. Pushing n elements one by one costs O(n log n). If you already have the data as an array, always heapify; prefer repeated insert only for a live stream where elements arrive one at a time.
Can a heap beat a balanced BST for Top K?
Both support insert and delete-min/max in O(log n), but a heap uses a flat array with no pointers, so it is faster in practice and simpler to write in an interview. Only use a BST if you also need range queries.
Now explain heaps to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.