Heaps and top-K
A size-K min-heap keeps the K largest items seen so far; its top is the answer and everything smaller is discarded.
Kth Largest Element in an Array. Return the k-th largest element of nums (in sorted order, not the k-th distinct).
Signals that point here
- "Top K", "K closest", "K most frequent", "Kth smallest".
- Streams: you cannot hold all the data, or you must answer after every insert.
- Merging
Ksorted lists, scheduling by priority, running median (two heaps).
The idea
Keep a min-heap of at most k items. Any item smaller than the heap's top cannot be among the k largest, so when the heap grows past k, pop the minimum.
In an interview, name the alternatives: sorting is O(n log n); quickselect is O(n) on average but O(n²) worst case and mutates the array; the heap is O(n log k) and works on a stream. Pick based on k, memory and whether data arrives online.
import heapq
def kth_largest(nums: list[int], k: int) -> int:
heap: list[int] = [] # min-heap of the k largest so far
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap[0]public static class Heaps
{
public static int KthLargest(int[] nums, int k)
{
var heap = new PriorityQueue<int, int>(); // min-heap by priority
foreach (int x in nums)
{
heap.Enqueue(x, x);
if (heap.Count > k) heap.Dequeue(); // drop the smallest
}
return heap.Peek();
}
}Complexity
O(n log k) time, O(k) space.
Pitfalls interviewers watch for
- Using a max-heap of all
nitems (O(n log n),O(n)space) and calling it a heap solution. - Python's
heapqis a min-heap only; for a max-heap push-x. - In C#,
PriorityQueuedequeues the smallest priority; for max-first use a reversed comparer or negate.
Variants worth knowing
- K most frequent: count, then a size-K heap keyed by count.
- Merge K sorted lists: heap of (value, list index, position).
- Running median: a max-heap for the lower half and a min-heap for the upper half.
Test it like the interviewer will
kth_largest([3, 2, 1, 5, 6, 4], 2)returns5kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)returns4kth_largest([1], 1)returns1kth_largest([-1, -1], 2)returns-1- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: kth_largest([3, 2, 1, 5, 6, 4], 2)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the
kmost frequent words, ties broken alphabetically. - Merge
ksorted linked lists into one sorted list. - Design a structure that returns the median after each inserted number.
Check yourself
Why a min-heap for the largest K?
The top is the weakest of the current top K, so it is the one to evict when something larger arrives.
When is quickselect the better answer?
Offline data, average-case O(n) is acceptable, and mutating the array is allowed.