The Top K Pattern in Depth

"Find the k largest", "the k most frequent" and "the k closest" are all the same problem in disguise. Here is how to solve all of them with one template.

What these problems look like

You are given n items and asked for the k best ones by some measure. The quick answer is to sort everything and slice off the first k, which costs O(n log n).

When k is much smaller than n, sorting does far more work than needed. You only have to remember the k best items seen so far.

A heap of size k does exactly that.

The optimized approach:

Use a min heap for the k largest items, and a max heap for the k smallest.
Push each item onto the heap.
When the heap holds more than k items, pop its top. That removes the worst of the current candidates.
After the scan, the heap holds the answer. In Python: heapq.heappush(heap, x), then heapq.heappop(heap) whenever len(heap) > k.

Complexity Analysis:

Every push and pop is O(log k)
The heap never holds more than k + 1 items
Time: O(n log k) for n pushes and at most n pops
Space: O(k) for the heap itself

1. Motivation

Suppose a game needs to show its three highest scores as new scores arrive.

The simplest approach sorts every score from high to low and keeps the first three.

Easy to write, but sorting costs O(n log n) every time, even though only three scores matter.

Can we do less work?

2. A Heap of Size k

Keep a min heap holding at most k scores.

Push every new score. If the heap grows past k, pop the smallest. The heap always holds the k best scores seen so far.

The root is the weakest of the top three, so it is the one evicted when a better score shows up.

import heapq

def top_k(scores, k):
    heap = []
    for s in scores:
        heapq.heappush(heap, s)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

3. Complexity

The heap never holds more than k + 1 scores, so each push and pop is O(log k).

Each of the n scores is pushed once and popped at most once: O(n log k) time.

The heap is the only extra storage: O(k) space.

k = 3 slots, no matter how large n gets

4. Where It Shows Up

These problems all use the same template with a different measure of "best":

Kth Largest Element in an Array: keep the k largest values
Top K Frequent Elements: compare by count
K Closest Points to Origin: compare by distance, using a max heap
Kth Largest Element in a Stream: keep the heap between calls

When the measure is "smallest", flip to a max heap by pushing negated keys.