Top-K with a heap

For this lesson, we'll focus on the Top-K pattern, not heap internals. We'll use Java's PriorityQueue as a bounded heap, cover K largest, K smallest, Top-K by frequency, K closest points, Kth largest and streaming feeds, then compare heap, sort and quickselect honestly. If you need the array layout, sift-up, sift-down and comparator rules first, read PriorityQueue and binary heaps.

01Picture it first: a tiny winners room

Imagine a live leaderboard with room for 3 scores. The room is a min-heap, so the lowest score inside stands at the door. A new score that is not higher gets turned away; a higher score enters and the old lowest score leaves.

That is why the heap direction feels backwards at first. For K largest, the heap root is the loser among the winners.

Fig. 1

The stream 5, 1, 9, 3, 7 fills a size-3 min-heap, then 3 evicts 1 and 7 evicts 3, leaving top 3 values 9, 7 and 5

Notice what we are not doing. We are not keeping every score, and we are not maintaining a fully sorted list of winners after every item. We maintain just enough order to know which retained candidate is easiest to evict.

02Top-K under the hood: size-K min-heap

Here is the compact version you will see in many solutions: offer every number, then evict when the heap grows past K.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

final class TopKLargestSimpleDemo {
    static List<Integer> topKLargest(int[] numbers, int k) {
        if (k <= 0) return List.of();

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int number : numbers) {
            heap.offer(number);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        List<Integer> result = new ArrayList<>(heap);
        result.sort(Collections.reverseOrder());
        return result;
    }

    public static void main(String[] args) {
        System.out.println(topKLargest(new int[] {5, 1, 9, 3, 7}, 3)); // [9, 7, 5]
    }
}

Notice three things:

• The heap never holds more than k + 1 elements, and after the eviction it holds at most K.
• Duplicates count as separate values. If the input is {9, 9, 8} and k = 2, the answer is [9, 9] unless the problem says distinct.
• The result is explicitly sorted because iterating a PriorityQueue is heap order, not sorted order.

The slightly better version avoids heap writes for values that cannot enter the top K. Once the heap is full, compare with peek() first.