Heap / priority queue: how to spot it
We'll cover the following
A heap always gives you the smallest (or largest) item in O(1) and lets you add or remove one in O(log n). It is the tool for "the best k of many" without sorting everything.
How the question sounds
- Top k, kth largest, kth smallest, or k most frequent
- Merge k sorted lists or streams
- Always need the current minimum or maximum while data keeps changing
- Median of a stream (two heaps)
- Scheduling the next most urgent task
The two shapes
Where it shows up in GenAI work
Top-k and nucleus sampling pick the best candidate tokens from a large vocabulary. Beam search keeps the k best partial sequences in a heap. Retrieval returns the top-k nearest chunks, and a priority queue schedules the most urgent requests in a serving system.
Is it heap / priority queue?
Decide yes or no before you open each answer.
Check yourselfReturn the k most frequent words in a document.
Yes. Count with a map, then keep the top k with a heap.
Check yourselfMerge k sorted lists into one sorted list.
Yes. A heap of the k current fronts gives the next smallest.
Check yourselfFind the median of numbers arriving in a stream.
Yes. Two heaps split the data into halves around the median.
Check yourselfFind a target in a sorted array in O(log n).
No. Sorted data and log n means binary search.
Check yourselfFind the longest substring with no repeats.
No. A moving range, so sliding window.
Check yourselfCheck that brackets are balanced.
No. The latest opener must close first, which is a stack.
Problems in this pattern
- Build a heap and pop it · Easy · Heap basics
- Kth largest in a stream · Medium · Top-k
- Merge k sorted lists · Hard · Merge
- Median of a stream · Hard · Two heaps
Summary: say it in the interview
- Top-k: Keep a min-heap of size k. Anything smaller than the root cannot be in the top k, so memory stays small.
- Two heaps: A max-heap for the small half and a min-heap for the large half give you the middle in O(1).