Keeping the k Largest in a Max-Heap

"Largest" suggests a max-heap, but a max-heap capped at k throws away the best item each time and keeps the k smallest.

Keeping the k largest items needs a min-heap, because a capped heap always throws away its top, and the top of a max-heap is the largest item. The reflex runs the other way: the question says largest, a max-heap gives the largest, so a max-heap seems right. Uncapped it is right but costly, since it holds all n items; capping it at k to save that space keeps exactly the wrong k. Two heaps capped at 2 over 14 3 22 9 17 1 show it.

The two listings are the same except for the heap's order: the first pushes negated values to make heapq a max-heap, and the second uses heapq as it is.

A max-heap and a min-heap, each capped at 2

max_capped.pypy

import heapq

values = [14, 3, 22, 9, 17, 1]
heap: list[int] = []
for value in values:
    heapq.heappush(heap, -value)
    if len(heap) > 2:
        heapq.heappop(heap)
print("kept:", sorted(-v for v in heap))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

kept: [1, 3]

min_capped.pypy

import heapq

values = [14, 3, 22, 9, 17, 1]
heap: list[int] = []
for value in values:
    heapq.heappush(heap, value)
    if len(heap) > 2:
        heapq.heappop(heap)
print("kept:", sorted(heap))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

kept: [17, 22]

The max-heap keeps 1 and 3, the two smallest. Each time it grows past two it pops its top, the largest it holds: 22 as soon as it arrives, then 14, 17 and 9. The min-heap pops its smallest each time and keeps 17 and 22. Nothing fails, and on inputs that arrive in falling order the two can even agree for a while. The rule is to name the item to throw away: the k largest throw away the smallest, so they need a min-heap, and the k smallest or the k closest throw away the largest, so they need a max-heap.

Heaps

On the Coding Interview Patterns cheatsheet

← → move through sections and cards