Topic 11 of 20
Always know the smallest or largest item in O(1): top-K, k-way merge, scheduling and running medians.
A heap (priority queue) is a complete binary tree stored in an array, where every parent is smaller than its children (a min-heap) or larger (a max-heap). You can read the top element in O(1) and push or pop in O(log n). Whenever a problem keeps asking "what is the smallest/largest/most urgent item right now?", a heap is the tool.
Four patterns cover almost every interview question. Top-K: keep a heap of size k, so finding the k largest of n items costs O(n log k) instead of a full sort. K-way merge: push the head of each sorted list and repeatedly pop the minimum. Two heaps: a max-heap for the lower half and a min-heap for the upper half give a running median. Greedy scheduling: sort by one attribute and use a heap to pick the best available option by another.
Know your language's heap API cold (heapq in Python, PriorityQueue in Java, priority_queue in C++), including how to build a max-heap and how to push tuples with a tie-breaker.
The basic size-k min-heap for a stream.
Straightforward max-heap simulation.
Ranking with a heap or a sort; a quick API drill.
Heap vs quickselect trade-offs; asked everywhere.
Top-K by a custom key; a Meta and Amazon staple.
Top-K with tie-breaking comparators.
Greedy counting or heap simulation with cooldowns.
Always place the most frequent remaining character.
A feed design using k-way merge of timelines.
Lazy frontier expansion from sorted arrays.
Generating an ordered sequence without duplicates.
Save ladders for the biggest climbs using a heap.
Fix the minimum by sorting and keep the best k sums in a heap.
Two heaps with lazy deletion inside a window.
K-way merge while tracking the current range.