Skip to content
Tutorials Center
My learning

Topics

Lesson 108 of 225 ยท Heaps

Top-K and Streaming Problems

Solve top-k problems in Python with a size-k heap: k largest numbers, kth largest in a stream, k most frequent words and k closest points, with complexity.

"Find the 10 best-selling products." "Show the 5 nearest restaurants." "Keep the 100 highest scores seen so far." These are top-k problems, and they appear everywhere, from search ranking to leaderboards to interview questions. The obvious solution is to sort everything and take the first k. That works, but it does far more work than needed, and it fails completely when the data is an endless stream you cannot store.

The size-k heap technique solves the whole family with a heap of at most k items. In this lesson you will see the brute-force approach first, learn why a min-heap finds the largest items, and then apply the same idea to the kth largest number, the most frequent words and the closest points. If you have not yet seen heaps, read Binary Heaps and Heaps in Python: heapq first.

Brute force: sort everything

Sort the data in descending order and take the first k items.

  • Time: O(n log n) to sort.
  • Space: O(n) if you copy the data (or O(1) extra if you sort in place).
  • Streaming: impossible without storing every item.

For n = 1,000,000 and k = 10 you would spend effort ordering a million items when you only care about ten. Can we do better?

The size-k heap idea

Keep a min-heap that never holds more than k items. It contains the best k items seen so far, and its root is the weakest of the winners, the smallest of the current top k.

For every new item x:

  1. If the heap has fewer than k items, push x.
  2. Otherwise compare x with the root (heap[0]). If x is bigger, it deserves a place: replace the root with x (one heapreplace or heappushpop). If it is not bigger, ignore x.

At the end, the heap holds exactly the k largest items.

TEXT
k = 3, stream: 5, 1, 9, 3, 7, 8

read 5    heap [5]
read 1    heap [1, 5]
read 9    heap [1, 5, 9]            full (3 items); root 1 is the weakest winner
read 3    3 > 1  -> replace 1       heap [3, 5, 9]
read 7    7 > 3  -> replace 3       heap [5, 7, 9]
read 8    8 > 5  -> replace 5       heap [7, 8, 9]

result: the 3 largest are 7, 8, 9

Why a min-heap to find the largest? Because you need fast access to the item you would evict, and that is the smallest of the winners. A max-heap would hand you the best item, which is useless for deciding who to kick out.

Complexity: each of the n items costs O(1) to compare with the root, and at most O(log k) if it replaces the root. Total time is O(n log k), and space is O(k). For k = 10 and n = 1,000,000, log k is about 3, so this is much cheaper than a full sort.

Python Top k with a size-k min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting inside the print is only for display. The algorithm itself never sorts the heap. Python's heapq.nlargest(k, data) implements this idea (see the end of the lesson).

Kth largest element

The kth largest is the root of the size-k min-heap, because it is the smallest of the k largest. For [3, 2, 1, 5, 6, 4] and k = 2, the top two are 6 and 5, and the 2nd largest is 5.

The same idea works for a stream where numbers arrive one at a time and you must answer "what is the kth largest so far?" after each. Memory stays O(k), and every add costs O(log k).

Python Kth largest in a stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you need the kth largest of a fixed list just once, there is also quickselect, an adaptation of quicksort's partitioning that runs in O(n) on average. A heap is better for streams and for repeated queries; quickselect wins for one-off queries on data in memory.

Top-k most frequent elements

Given words, return the k most frequent. This takes two steps: count with a dictionary, then pick the top k counts.

Brute force: count, then sort all distinct items by count: O(n + m log m), where m is the number of distinct items.

Heap: count in O(n), then push (count, item) pairs into a size-k min-heap: O(n + m log k).

Bucket sort: counts are at most n, so make a list of buckets indexed by count, and read from the highest bucket down. This runs in O(n) time and O(n) space. It is the fastest, but the heap is simpler to extend and works for any score, not only whole-number counts.

Be careful with ties. If two words have the same count, which comes first? A clean rule is "higher count first, then alphabetical". With a min-heap of (count, word) the alphabetical tie-break would be backwards for words (the heap evicts the smaller word, keeping the larger), so the code below uses nsmallest on (-count, word) pairs, which encodes the rule directly.

Python k most frequent words: sort, heap and buckets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

"the" appears 4 times, and "and" and "cat" are tied with 3. Our rule breaks the tie alphabetically, so all three of our methods return the and and. The standard library's Counter.most_common(k) is a one-liner that uses heapq.nlargest internally, but it breaks ties by first appearance, so it returns the and cat here. Use it in real code when you do not care about the tie rule.

K closest points to the origin

Given points (x, y), return the k closest to (0, 0). The distance is sqrt(xยฒ + yยฒ), but you can compare squared distances and skip the square root: it is faster and exact for integers.

This is a top-k problem with the order reversed: we keep the k smallest distances, so the item to evict is the largest distance. That means a max-heap of size k. With heapq, negate the distance.

TEXT
keep the k closest so far in a max-heap (by distance)
new point farther than the root?   -> ignore it
new point closer than the root?    -> replace the root
the root is always the farthest of the current winners
Python K closest points with a size-k max-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

K largest sums from two arrays

Given arrays a and b (each of size n), list the k largest values of a[i] + b[j] over all pairs. There are nยฒ pairs, so enumerating them all costs O(nยฒ log n). Use the heap idea in a smarter way: sort both arrays in descending order. The largest sum is a[0] + b[0]. After taking (i, j), the next candidates are (i + 1, j) and (i, j + 1), because each is no larger than (i, j). Keep a max-heap of frontier pairs and a seen set so no pair is pushed twice.

Python k largest pair sums with a frontier heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n log n + k log k) with O(k) heap size, instead of O(nยฒ). The same "expand to the two neighbors" pattern works for the k smallest sums, k-th smallest in a sorted matrix, and merging sorted lists lazily.

Counting the work

Big-O says the size-k heap is cheaper. You can see it by counting comparisons. The wrapper class below counts every < between two numbers:

Python Counting comparisons: sort versus size-k heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The heap checks each item against the root (one comparison), and only the few items that beat the root cause a sift. For random data that is a handful of extra comparisons in total, so the count is close to n, while sorting needs roughly n log n.

Choosing the right tool

Situation Best approach
k = 1 max() / min(), O(n)
small k, large n, or a stream size-k heap, O(n log k), O(k) memory
k close to n sort, O(n log n)
kth element of a static list, once quickselect, O(n) average
most frequent, counts are small integers bucket sort, O(n)
top k queried again and again on changing data keep the heap alive; each update is O(log k)

Common mistakes

  • Using a max-heap to find the k largest. You need the minimum of the winners at the root, so use a min-heap. The mirror image applies to k smallest and k closest.
  • Pushing everything and popping k times. That costs O(n log n) time and O(n) memory, the same as sorting.
  • Forgetting that heap[0] is only the kth largest when the heap is full. With fewer than k items, the root is not the answer.
  • Ignoring ties. Decide the tie-break rule, and encode it in the tuple you push.
  • Comparing unsorted heap lists. The heap array is not sorted; sort the final result if the order matters.
  • Using square roots. They add floating-point error and cost for nothing, because squared distances order the points identically.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. To find the 5 largest numbers in a stream, which heap do you keep?

    The root of a min-heap is the smallest of the current top 5, which is exactly the one to evict when a bigger number arrives.
  2. 2. What is the time complexity of the size-k heap method for n items?

    Each of the n items costs one comparison with the root and at most one O(log k) heap operation.
  3. 3. In the 'k closest points' problem we keep a max-heap of size k. Why a max-heap?

    We want the k smallest distances. The item we may need to remove is the largest distance among them, so it must be at the root. With heapq, store negated distances.
  4. 4. A stream has 3 items so far and k = 5. What is heap[0]?

    Until the heap holds k items, its root is just the smallest item seen so far, not the kth largest.
  5. 5. Which approach finds the k most frequent items in O(n) time?

    Counts never exceed n, so you can place each item in the bucket for its count and read buckets from the highest index down, in O(n) total.

Summary

  • Top-k problems ask for the k best items by some score. Sorting everything costs O(n log n) and needs all the data in memory.
  • The size-k heap keeps the current k winners in a heap of size k. For k largest use a min-heap, because the root is the weakest winner. Replace the root when a better item arrives.
  • Time is O(n log k) and memory is O(k), and it works on streams.
  • The kth largest is the root of the full size-k min-heap. KthLargest answers in O(log k) per new number.
  • For k most frequent, count with a dictionary and then use a heap, or use buckets for O(n). For k closest, keep a max-heap by squared distance.
  • heapq.nlargest, nsmallest and Counter.most_common already implement the technique.

Next: Running Median and Two Heaps