Topic 11 of 20
Heaps / Priority Queue
Always know the smallest or largest item in O(1): top-K, k-way merge, scheduling and running medians.
The concept
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.
Patterns you will learn
Problems, in order
- 1
The basic size-k min-heap for a stream.
Top-K with a Size-K HeapReported at: GoogleAmazonMeta+2 - 2
Straightforward max-heap simulation.
Max-Heap SimulationReported at: AmazonVisaNvidia+1 - 3
- 4Relative RanksEasy
Ranking with a heap or a sort; a quick API drill.
Heap / SortingReported at: Google - 5
Heap vs quickselect trade-offs; asked everywhere.
Top-K / QuickselectReported at: MetaAmazonMicrosoft+6 - 6
Top-K by a custom key; a Meta and Amazon staple.
Top-K with a Size-K HeapReported at: MetaAmazonMicrosoft+2 - 7Top K Frequent WordsMedium
Top-K with tie-breaking comparators.
Top-K with Custom OrderingReported at: AmazonMicrosoftGoogle+4 - 8Task SchedulerMedium
Greedy counting or heap simulation with cooldowns.
Greedy Scheduling with a HeapReported at: AmazonMetaMicrosoft+1 - 9Reorganize StringMedium
Always place the most frequent remaining character.
Greedy with a Max-HeapReported at: AmazonMetaGoogle+2 - 10
- 11Design TwitterMedium
A feed design using k-way merge of timelines.
K-way MergeReported at: GoogleAmazonWalmart Global Tech - 12
Lazy frontier expansion from sorted arrays.
K-way MergeReported at: AppleAmazonLinkedIn+1 - 13Ugly Number IIMedium
Generating an ordered sequence without duplicates.
Heap / Multiple PointersReported at: Microsoft - 14
- 15
Save ladders for the biggest climbs using a heap.
Greedy with a Min-HeapReported at: AmazonGoogleMicrosoft - 16
Fix the minimum by sorting and keep the best k sums in a heap.
- 17
- 18
Two heaps with lazy deletion inside a window.
Two Heaps + Lazy DeletionReported at: MetaMicrosoftSpotify - 19
- 20
K-way merge while tracking the current range.