Heap Top-K Problems: When to Use a Min-Heap

By Hourly DSA · September 21, 2026 · 4 min read

To keep the k largest values seen so far, use a min-heap of at most k elements. Its smallest value is the weakest member of the current top k, so it is the one to replace when a larger value arrives.

That direction can feel backward at first. You want large values in the result, but you need quick access to the smallest value you are still willing to keep.

What does a heap guarantee?

A binary min-heap keeps each parent no larger than its children. Its root is therefore the minimum. A max-heap reverses that order, keeping the maximum at the root.

The entire structure is not sorted. Knowing the root is smallest does not tell you the order of two siblings or of every element in the backing array.

For a binary heap of size k, inspecting the root takes O(1) time. Insertion and removal of the root take O(log k) time for k at least two. Princeton's priority queue chapter explains the heap operations and their use in retaining the largest records from a stream.

Trace the three largest values

Find the three largest values in:

[6, 2, 9, 4, 8, 1, 7]

Start by retaining 6, 2, and 9. The minimum among those candidates is 2.

When 4 arrives, it beats 2, so replace 2 with 4. When 8 arrives, it beats the new minimum, 4. When 1 arrives, discard it because it cannot improve the candidates. Finally, 7 replaces 6.

Value just processed	Retained values, shown sorted	Smallest retained value
First three values	2, 6, 9	2
4	4, 6, 9	4
8	6, 8, 9	6
1	6, 8, 9	6
7	7, 8, 9	7

The table sorts candidates for readability; it does not show their internal heap layout.

The final retained values are 7, 8, and 9. The root, 7, is the third-largest value. You don't need to sort the retained values if that single rank is all the question asks for.

Why discarding a small value is safe

Once the heap is full, every retained value is at least as large as its root. If the next value is smaller than the root, there are already k values that are larger.

That new value cannot enter the top k among the processed elements. Future arrivals can only add more competition, so discarding it cannot lose a future top-k answer.

After every step, the heap contains the k largest values from the processed prefix, or all processed values if fewer than k have arrived. This invariant explains the algorithm better than “use a heap for top k.”

Do duplicates count?

Unless the problem says “distinct,” repeated values usually occupy separate ranks. The two largest values in [9, 9, 5] are 9 and 9.

If the task asks for distinct values, duplicate handling becomes an extra requirement. Don't silently remove repetitions from a problem where each occurrence counts.

Also settle the valid range of k. For a kth-largest query, require 1 <= k <= n. A request for zero results can return an empty collection, but “zeroth largest” has no usual meaning.

Compare a heap with sorting

Sorting the whole array takes O(n log n) time with a comparison sort and gives you a complete order. That may be useful if the next task needs that order too.

Keeping a heap of k candidates takes O(n log k) time for k at least two and O(k) heap space. For k equal to one, a running maximum gives O(n) time and O(1) space. The heap approach can process incoming values without retaining the full input.

If you need the final k values in sorted order, include the additional O(k log k) sorting or extraction cost. A heap does not make that output order free.

When k is close to n and the input is already available, sorting may be the clearer choice. A small k or a stream makes bounded heap storage more useful.

Reverse the question

To keep the k smallest values, use a max-heap of k candidates. Its root is now the largest retained value, which is the candidate to replace when a smaller value arrives.

For [5, 1, 8, 3] and k equal to two, the two smallest values are 1 and 3. A max-heap over those candidates exposes 3 as the current cutoff.

Practice asking, “Which retained item would I evict next?” That often reveals the heap direction. Pair Hourly DSA concept practice with our Big O guide and stack vs. queue comparison to distinguish priority order from arrival order.