must-know mid · part of Skills & Topics · Senior SWE Roadmap · related: Arrays & Strings · Sorting & Searching Algorithms · Complexity Analysis · Graphs — Shortest Path
Why heaps exist / recognition signals
A heap answers one question fast, over and over, while the data keeps changing: “what’s the current min (or max)?” Sorting the whole collection gives you that answer too, but re-sorting after every insert/removal is O(n log n) each time. A heap keeps just enough order — the root is always the extreme — while insert and remove-extreme both stay O(log n), and it never bothers fully ordering the rest of the elements because nothing ever asks for that.
Recognition signals:
- “kth largest/smallest”, “top K frequent”, “K closest points” → heap of size K
- “median of a running stream” → two heaps (max-heap for the lower half, min-heap for the upper half)
- “merge K sorted lists/arrays” → min-heap holding one candidate from each list
- “schedule by priority/deadline”, “process the most urgent item next” → priority queue as the core data structure, not just a helper
- “reorganize so no two adjacent share a property” (e.g. task scheduler, rearrange string) → max-heap by frequency
Binary heap: array representation
A binary heap is a complete binary tree (every level full except possibly the last, filled left to right) stored flat in an array — no pointers needed, because the tree shape is implicit in the indices:
parent(i) = (i - 1) / 2 left(i) = 2i + 1 right(i) = 2i + 2
flowchart TD subgraph Tree["Min-heap as a tree"] N0["idx 0: 1"] --> N1["idx 1: 3"] N0 --> N2["idx 2: 2"] N1 --> N3["idx 3: 5"] N1 --> N4["idx 4: 9"] N2 --> N5["idx 5: 8"] end
flowchart LR subgraph Array["Same heap, as array = [1, 3, 2, 5, 9, 8]"] direction LR A0["idx0: 1"] --- A1["idx1: 3"] --- A2["idx2: 2"] --- A3["idx3: 5"] --- A4["idx4: 9"] --- A5["idx5: 8"] end Note["parent(1)=0, parent(2)=0 → idx1,idx2 are children of root parent(3)=1, parent(4)=1 → idx3,idx4 are children of idx1 parent(5)=2 → idx5 is the child of idx2"]
The heap property (min-heap: every parent ≤ its children) only constrains parent-child relationships, not siblings — that’s deliberately weaker than a full sort, and that weakness is exactly what makes insert/remove O(log n) instead of O(n log n).
Sift-up (insert) and sift-down (extract) mechanics
Insert: append the new value at the end of the array (the next open leaf slot), then sift up — swap with its parent while it’s smaller than that parent, walking toward the root.
Extract-min: the root is always the answer. Move the last element into the root slot, shrink the array by one, then sift down — swap with the smaller child while it’s bigger than that child, walking toward the leaves.
Worked example: building a min-heap by inserting 5, 3, 8, 1, 9, 2
| Insert | Array before | New index | Sift-up comparisons | Array after |
|---|---|---|---|---|
| 5 | [] | 0 | none (root) | [5] |
| 3 | [5] | 1 | parent(idx0)=5 > 3 → swap | [3,5] |
| 8 | [3,5] | 2 | parent(idx0)=3 < 8 → stop | [3,5,8] |
| 1 | [3,5,8] | 3 | parent(idx1)=5>1→swap; parent(idx0)=3>1→swap | [1,3,8,5] |
| 9 | [1,3,8,5] | 4 | parent(idx1)=3 < 9 → stop | [1,3,8,5,9] |
| 2 | [1,3,8,5,9] | 5 | parent(idx2)=8>2→swap; parent(idx0)=1<2→stop | [1,3,2,5,9,8] |
Final heap array: [1, 3, 2, 5, 9, 8].
Worked example: extract-min (sift-down) from [1, 3, 2, 5, 9, 8]
| Step | Action | Array |
|---|---|---|
| 1 | Remove root (1); move last element (8) into root slot | [8,3,2,5,9] |
| 2 | Compare idx0=8 against children idx1=3, idx2=2 → smallest child is idx2 (2) | — |
| 3 | 8 > 2 → swap(idx0, idx2) | [2,3,8,5,9] |
| 4 | idx2’s children would be idx5, idx6 — out of bounds (size 5) → stop | [2,3,8,5,9] |
extract-min returns 1; the heap is now [2,3,8,5,9].
sequenceDiagram participant Root as idx0 participant L as left child idx1 participant R as right child idx2 Note over Root: extract-min: move last element (8) into the root Root->>L: compare 8 vs 3 Root->>R: compare 8 vs 2 Note over Root,R: smallest child is idx2 (2) → swap Root->>R: swap(idx0, idx2) Note over R: 8 is now at idx2; its children (idx5,idx6) don't exist → sift-down stops
Java — heap mechanics (manual array-backed min-heap)
public class MinHeap {
private final int[] heap;
private int size = 0;
public MinHeap(int capacity) {
heap = new int[capacity];
}
public void insert(int value) {
heap[size] = value;
siftUp(size);
size++;
}
private void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[parent] <= heap[i]) break;
swap(parent, i);
i = parent;
}
}
public int extractMin() {
int min = heap[0];
heap[0] = heap[--size];
siftDown(0);
return min;
}
private void siftDown(int i) {
while (true) {
int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest == i) break;
swap(i, smallest);
i = smallest;
}
}
private void swap(int a, int b) {
int tmp = heap[a];
heap[a] = heap[b];
heap[b] = tmp;
}
}Python — heap mechanics (manual list-backed min-heap)
class MinHeap:
def __init__(self) -> None:
self._heap: list[int] = []
def insert(self, value: int) -> None:
self._heap.append(value)
self._sift_up(len(self._heap) - 1)
def _sift_up(self, i: int) -> None:
while i > 0:
parent = (i - 1) // 2
if self._heap[parent] <= self._heap[i]:
break
self._heap[parent], self._heap[i] = self._heap[i], self._heap[parent]
i = parent
def extract_min(self) -> int:
min_val = self._heap[0]
last = self._heap.pop()
if self._heap:
self._heap[0] = last
self._sift_down(0)
return min_val
def _sift_down(self, i: int) -> None:
n = len(self._heap)
while True:
left, right, smallest = 2 * i + 1, 2 * i + 2, i
if left < n and self._heap[left] < self._heap[smallest]:
smallest = left
if right < n and self._heap[right] < self._heap[smallest]:
smallest = right
if smallest == i:
break
self._heap[smallest], self._heap[i] = self._heap[i], self._heap[smallest]
i = smallestIn practice nobody hand-rolls a heap in production code or most interviews — java.util.PriorityQueue and Python’s heapq exist precisely so you don’t. The manual version above is worth knowing because “explain what’s happening inside PriorityQueue.offer()” is a fair follow-up question.
The top-K pattern: heap of size K instead of sorting everything
The single most common heap interview pattern: instead of sorting all n elements (O(n log n)) and taking the first/last K, maintain a heap that never grows past size K. For “K largest,” use a min-heap of size K — counter-intuitively the smaller extreme is what you track, because the root of that min-heap is the smallest of your current top-K, i.e. exactly the element to evict the instant something bigger shows up. Every one of the n elements does O(log k) work instead of O(log n), for a total of O(n log k) — a real win when k << n.
The same trick generalizes: Merge K Sorted Lists keeps a min-heap holding just the current head of each of the K lists (not all N total elements) — pop the smallest, push its successor, repeat. That’s O(N log K) instead of O(N·K) from pairwise merging.
Java — Kth Largest Element in a Stream (LeetCode 703)
import java.util.PriorityQueue;
public class KthLargest {
private final int k;
private final PriorityQueue<Integer> minHeap; // capped at size k; root = kth largest so far
public KthLargest(int k, int[] nums) {
this.k = k;
this.minHeap = new PriorityQueue<>();
for (int n : nums) {
add(n);
}
}
public int add(int val) {
minHeap.offer(val);
if (minHeap.size() > k) {
minHeap.poll(); // discard the smallest — it can never be the kth largest again
}
return minHeap.peek();
}
}Python — Kth Largest Element in a Stream
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]) -> None:
self.k = k
self.heap = nums[:]
heapq.heapify(self.heap) # O(n) build, not O(n log n)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # discard the smallest
return self.heap[0]Python’s heapq is min-heap only — simulating a max-heap means pushing negated values and negating again on read.
Complexity comparison
| Operation | Time | Notes |
|---|---|---|
| Peek min/max | O(1) | it’s the root |
| Insert (sift-up) | O(log n) | bubbles up at most the tree height |
| Extract min/max (sift-down) | O(log n) | bubbles down at most the tree height |
Build heap from n elements (heapify) | O(n) | bottom-up heapify, not O(n log n) — see pitfalls |
| Top-K via full sort | O(n log n) time, O(n) space | sorts everything even though only k values are needed |
| Top-K via heap of size k | O(n log k) time, O(k) space | never holds more than k elements at once |
| Merge K sorted lists (N total elements) | O(N log K) time, O(K) space | heap holds one candidate per list, not all N |
Common pitfalls
- Max-heap instead of min-heap for “K largest”: the correct structure is a min-heap capped at size K — its root is the smallest of the current top-K, i.e. the eviction candidate. A max-heap of everything works but does O(log n) per insert on every element, defeating the point of bounding by K.
- Assuming heap order == sorted order: the array backing a heap only guarantees the root is extreme — iterating it directly does not yield a sorted sequence. Popping repeatedly does.
- Forgetting Python’s
heapqis min-only: max-heap behavior requires negating values on push and pop, and it’s easy to forget to negate back when reading the value out. - Missing the size cap: forgetting to pop back down to size K after every push turns an O(n log k) top-K solution into an accidental O(n log n) one, silently.
- Building a heap via n sequential inserts instead of
heapify: n inserts is O(n log n); bottom-up heapify from a full array is O(n) — because most nodes sit near the leaves where sift-down does almost no work, and the per-level work sums geometrically to O(n) rather than n·O(log n). - Using a heap when order statistics/range queries are actually needed: a heap only answers “what’s the extreme,” not “what’s the 5th smallest right now” or “how many elements are between X and Y” — that calls for a balanced BST (TreeMap/TreeSet) instead.
Practice problems
- Kth Largest Element in a Stream (heap of size k, streaming)
- Kth Largest Element in an Array (heap vs. quickselect tradeoff — ties to Sorting & Searching Algorithms)
- Top K Frequent Elements (heap of size k on frequency counts, or bucket sort in O(n))
- K Closest Points to Origin (max-heap of size k on squared distance)
- Merge K Sorted Lists (min-heap of list heads)
- Find Median from Data Stream (two heaps: max-heap for the lower half, min-heap for the upper half)
- Task Scheduler (max-heap by remaining frequency)
- Meeting Rooms II (min-heap of meeting end times)
Interview angles
- “Why a min-heap of size K for ‘largest K,’ not a max-heap of everything?” — the min-heap’s root is exactly the eviction threshold for the current top-K, giving O(n log k) total instead of O(n log n); a full max-heap does unnecessary O(log n) work on elements that will never make the final K.
- “Why is building a heap from an array O(n), not O(n log n)?” — bottom-up heapify: most nodes are near the leaves where sift-down is nearly free; summing the (decreasing) work per level across all
log nlevels telescopes to O(n), unlike n sequential inserts which really is O(n log n). - “How would you find the median of a running data stream?” — two heaps kept balanced within size 1 of each other: a max-heap for the lower half, a min-heap for the upper half; the median is the top of the larger heap, or the average of both tops when they’re equal size.
- “PriorityQueue/heapq vs. a balanced BST (TreeMap/TreeSet) for a top-K problem?” — a heap gives O(log n) insert and O(1) peek-extreme with a small constant factor, but can’t do arbitrary rank/floor/ceiling queries; a balanced BST does those in O(log n) too but with a heavier constant — use a heap when you only ever need the current extreme.
- “How do you merge K sorted lists efficiently?” — a min-heap holding the current head of each of the K lists; pop the smallest, push its successor from the same list; O(N log K) total, versus O(N·K) from repeated pairwise merges.
- “What happens to the heap-of-size-K advantage as K approaches N?” — it disappears: O(n log k) approaches O(n log n) as k→n, so at that point a plain full sort is simpler and no slower.