Top K Elements

What is it?

When only the k best items matter, keep a heap holding exactly k candidates. Counter-intuitively you keep a min-heap to find the k largest: the smallest of your current winners sits at the top, ready to be evicted the moment something better arrives. The full input is never sorted.

The core idea

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

1import heapq2 3 4def k_largest(nums, k):5    """A MIN-heap of size k: its root is the weakest element still in the set."""6    heap = []7    for value in nums:8        heapq.heappush(heap, value)9        if len(heap) > k:10            heapq.heappop(heap)   # evicts the smallest, keeping the k largest11    return sorted(heap, reverse=True)12 13 14def k_most_frequent(items, k):15    counts = {}16    for item in items:17        counts[item] = counts.get(item, 0) + 118 19    heap = []20    for item, count in counts.items():21        heapq.heappush(heap, (count, item))22        if len(heap) > k:23            heapq.heappop(heap)24 25    return [item for _count, item in sorted(heap, reverse=True)]

Common mistakes

• Reaching for a max-heap to find the k largest — that requires holding all n elements instead of k.
• Pushing then popping in the wrong order, so the heap briefly holds k+1 items and evicts the wrong one.
• Assuming the heap iterates in sorted order; only the root is guaranteed.
• Ignoring ties when the problem specifies a tie-breaking rule.