Top-k Problems: Keep a Small Heap

The k largest

You get a million scores and want the top 3. Sorting all of them is O(n log n). Smarter: keep a min-heap of just k items – your current top k. The heap's top is the weakest of them. When a new score beats it, kick the weakest out:

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

public class Main {
    public static void main(String[] args) {
        int[] scores = {55, 91, 23, 78, 99, 64, 85, 12, 70};
        int k = 3;
        PriorityQueue<Integer> top = new PriorityQueue<Integer>();   // min-heap
        for (int s : scores) {
            top.offer(s);
            if (top.size() > k) top.poll();     // drop the weakest
        }
        System.out.println("k-th largest: " + top.peek());
        ArrayList<Integer> best = new ArrayList<Integer>(top);
        Collections.sort(best, Collections.reverseOrder());
        System.out.println("top " + k + ": " + best);
    }
}

Output

k-th largest: 85
top 3: [99, 91, 85]

Each score costs O(log k), so the whole thing is O(n log k) – and it only ever stores k items, so it works even when scores arrive one at a time and never end.

Think of it like this: A talent show with 3 chairs for finalists. A new act takes a chair only if it's better than the weakest finalist currently sitting – who then leaves.

Remember: For the k largest, use a min-heap of size k. For the k smallest, use a max-heap of size k. It feels backwards, but the top must be the one to kick out.