Heaps & Priority Queues — Controlling Extremes Fast
Learn how heaps provide O(log n) insertions and removals for extreme values, powering top-K, scheduling, and streaming problems.
Problem Statement
Understand how to model problems that repeatedly pull the smallest or largest element using heaps, and how to maintain heaps efficiently in interviews.
Why This Problem Matters
- Top-K, running median, and Dijkstra all rely on priority queues.
- Heaps illustrate trade-offs between constant factors and asymptotic guarantees compared to sorting every time.
- Interviewers expect you to articulate why a heap beats naive scanning for repeated extreme queries.
Thought Process
Choose min vs. max heap
Pick the heap that makes pushes and pops align with the “extreme” you need (largest K, smallest deadlines, etc.).
Size-management tactics
For top-K smallest, keep a max heap of size K; for top-K largest, use a min heap. Pop whenever size exceeds K.
Account for comparators
When building heaps for composite data, define ordering explicitly so ties are deterministic.
Step-by-Step Reasoning
- Pick the heap orientation (min or max).
- Push items with relevant priority data.
- Whenever heap size exceeds target, pop to maintain invariant.
- Extract or peek to answer the problem’s query (extreme element).
Dry Run
Find top 3 scores from stream [5, 1, 9, 3, 12]
Maintain a min heap size 3. After processing, heap contains 9, 12, 5—the three largest.
Merge k sorted lists
Push the first node of each list. Pop min, append to result, push next from same list. Continue until heap empty.
Complexity Analysis
Time
O(log n) per insertion/removal
Space
O(n)
Why
Binary heaps store elements in arrays; push/pop bubble up/down with logarithmic swaps while storing all elements.
Annotated Solution
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.NoSuchElementException;
public class HeapPatterns {
private static class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int value) {
data.add(value);
bubbleUp(data.size() - 1);
}
int pop() {
if (data.isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
int result = data.get(0);
int last = data.remove(data.size() - 1);
if (!data.isEmpty()) {
data.set(0, last);
bubbleDown(0);
}
return result;
}
int size() {
return data.size();
}
List<Integer> snapshot() {
return new ArrayList<>(data);
}
private void bubbleUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (data.get(parent) <= data.get(index)) {
break;
}
Collections.swap(data, parent, index);
index = parent;
}
}
private void bubbleDown(int index) {
int length = data.size();
while (true) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < length && data.get(left) < data.get(smallest)) {
smallest = left;
}
if (right < length && data.get(right) < data.get(smallest)) {
smallest = right;
}
if (smallest == index) {
break;
}
Collections.swap(data, index, smallest);
index = smallest;
}
}
}
public static List<Integer> topK(int[] nums, int k) {
MinHeap heap = new MinHeap();
for (int num : nums) {
heap.push(num);
if (heap.size() > k) {
heap.pop();
}
}
return heap.snapshot();
}
}Implementing a heap showcases mastery beyond library usage. Interviews often accept built-in priority queues, but demonstrating the array-backed structure builds credibility.
Common Pitfalls
- Letting heap size grow unbounded when only the top K items are required wastes memory.
- Forgetting to update composite priorities when the underlying data changes.
- Misinterpreting lexicographical vs. numerical ordering when comparing tuple elements.
Follow-Up Questions
- Explain how to implement a max heap by negating values or flipping comparator.
- Describe lazy deletion strategies when removals of arbitrary elements are required.
- Combine heaps with hash maps to achieve O(log n) priority updates (Indexed priority queue).