Top-k problems

To find the k largest items in a stream or a big list, keep a min-heap of size k: push each item, pop when the heap exceeds k. It runs in O(n log k) and never holds more than k items.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain why a min-heap of size k finds the k largest
Solve a top-k problem in O(n log k)
Spot the max-heap approach that holds every element

In practice

A few lines that show Top-k problems doing its job.

Python

import heapq

def top_k(items, k):
    heap = []
    for item in items:
        heapq.heappush(heap, item)
        if len(heap) > k:
            heapq.heappop(heap)       # drop the smallest kept so far
    return sorted(heap, reverse=True)

top_k([5, 1, 9, 3, 7], 2)             # [9, 7]
# or: heapq.nlargest(2, items)

The common mistake

Watch for

Using a max-heap for the k largest. The structure then holds every element and pops the biggest k at the end, which is O(n log n) and defeats the point.

What to know first

Your roadmap puts these before Top-k problems, unless you already know them.

How it stays learned

Once a session shows you understand Top-k problems, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Previous in the module← Building a heap