The top K pattern answers questions like “give me the K largest numbers” or “the K most frequent words” without sorting the entire input. The trick is a heap of fixed size K. As you stream through the data, you keep only the best K candidates seen so far, evicting the weakest whenever a stronger element arrives. This beats a full sort whenever K is much smaller than the input size.
When to use it#
Use a heap when the problem asks for the top, bottom, closest, or most frequent K of something, or for a running median. The counterintuitive part is the heap direction: to keep the K largest elements, use a min-heap of size K so the smallest of your kept elements sits on top and is cheap to evict. To keep the K smallest, use a max-heap.
Worked example#
Finding the K largest elements with a size-K min-heap:
1import heapq
2
3def k_largest(nums, k):
4 heap = [] # min-heap holding the k largest so far
5 for value in nums:
6 if len(heap) < k:
7 heapq.heappush(heap, value)
8 elif value > heap[0]:
9 heapq.heapreplace(heap, value) # pop smallest, push new
10 return sorted(heap, reverse=True)
11
12print(k_largest([3, 1, 5, 12, 2, 11], 3)) # [12, 11, 5]
Python’s heapq is a min-heap. For a max-heap, push negated values. heapq.nlargest and heapq.nsmallest wrap this pattern when you do not need the streaming behavior.
Complexity#
Time is O(n log k), since each of the n elements does at most a log k heap operation. Space is O(k) for the heap. When K approaches n, a plain sort at O(n log n) is comparable, so the heap wins most when K is small.
Practice problems#
- Kth Largest Element in an Array
- Top K Frequent Elements
- K Closest Points to Origin
- Find K Pairs with Smallest Sums
- Sort Characters by Frequency
- Find Median from Data Stream (two heaps)
Keep the Big-O cheat sheet nearby to weigh the heap against a full sort, and return to the pattern hub for the complete pattern map.