Know this before you start: “Keep only the k best items in a heap”

Keeping only the k best with a heap

For the k largest, keep a min-heap of size k: whenever it grows past k, pop the smallest. What's left are the k largest. O(n log k).

The idea

Sorting everything to take the top k costs O(n log n). A heap that never holds more than k items is cheaper when k is small.

For the k largest use a MIN-heap: its top is the weakest of the current best k, the one to kick out when something better arrives. At the end, the top is the k-th largest overall.

See it step by step

The 2 largest of [3, 2, 1, 5, 6, 4]

push 3, 2 → {2, 3}
push 1 → pop 1. push 5 → pop 2 → {3, 5}. push 6 → pop 3 → {5, 6}. push 4 → pop 4.
Left: {5, 6}. The 2nd largest is the top: 5.

In code (Python)

import heapq

def k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # drop the smallest of the k + 1
    return sorted(heap, reverse=True)

print(k_largest([3, 2, 1, 5, 6, 4], 2))   # [6, 5]
print(heapq.nlargest(2, [3, 2, 1, 5, 6, 4]))   # [6, 5], the built-in

O(n log k) time, O(k) space.

When you'll use it

k largest / smallest / closest / most frequent, k-th largest, streams where data keeps arriving.

Common mistakes

Using a max-heap for the k largest (it keeps the wrong end).
Pushing all n items then popping k (O(n log n), O(n) space).