Return the k most frequent elements from a large stream of values. Why not just sort by frequency?

Sorting answers a question you were not asked

A full sort produces a total order over every element. The question asks for a set of k items and, usually, nothing about the order among the rest. You are paying n log n comparisons to establish n log n bits of ordering information when the answer needs a boundary and a handful of members. That gap is the whole argument for a heap, and stating it in those terms is worth more than quoting the two complexities side by side.

A binary heap maintains only a partial order: every parent outranks its children, and nothing is known about siblings. That is weak enough to maintain in O(log n) per insertion and strong enough that the extreme element is always at the root in O(1). For top-K you need exactly that one guarantee, repeatedly.

The bounded heap

Count first, then select. The counting pass is O(n) with a hash map. The selection pass keeps a heap of at most k entries ordered so that the weakest survivor sits at the root, ready to be evicted.

Map<Integer, Integer> counts = new HashMap<>();
for (int value : stream) counts.merge(value, 1, Integer::sum);

// Min-heap on the count: the root is the weakest candidate currently held.
PriorityQueue<Map.Entry<Integer, Integer>> heap =
        new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
    heap.offer(entry);
    if (heap.size() > k) heap.poll();     // evict the smallest count, keeping the k largest
}

Each offer and poll costs O(log k) because the heap never exceeds k + 1 elements, so the selection pass is O(m log k) over m distinct keys, and the whole solution is O(n + m log k) time with O(m + k) space. When k is small relative to the data - the top ten of a million - log k is a small constant and the improvement over sorting is real rather than notational.

Use Comparator.comparingInt rather than a lambda that subtracts one count from another. Subtraction of two ints overflows for large magnitudes and silently returns a comparator that violates transitivity, which corrupts the heap rather than throwing. Integer.compare(a, b) is the safe hand-written form.

Getting the heap direction backwards

This is where otherwise correct candidates lose the question. To keep the k largest you need a min-heap, because the operation you perform repeatedly is discarding the smallest thing you are holding, and a heap only gives cheap access to its root. Reaching for a max-heap feels right - you want the largest, so order by largest - and it forces you into the wrong shape: a max-heap of all m elements followed by k polls, which is O(m + k log m) with every element resident. That is not catastrophic, but it defeats the memory argument that justified the heap in the first place, and on a stream too large to hold it is simply not an option.

Say the rule as a sentence: the heap holds the survivors, and its root is the next one you are willing to lose. That phrasing gets the direction right for smallest-K too, where the same logic inverts to a max-heap.

What the heap will not do for you

A heap is not a sorted collection, and Java's PriorityQueue makes that visible in a way people trip over: iterating it, printing it, or calling toString yields the internal array order, which is heap order and not sorted order. Only draining it with repeated poll gives a sorted sequence. It also has no efficient search - contains and remove(Object) are linear scans - so a design that needs to update the priority of an arbitrary element wants an indexed structure or a balanced tree instead.

Two alternatives deserve a mention before the interviewer asks. Quickselect partitions around a pivot and finds the k-th largest in O(m) expected time, which beats the heap, but it needs the entire array in memory, it reorders it, and its worst case is O(m²) without randomised pivots. And when the values being ranked are counts, they are bounded by n, so bucketing keys by count into an array of n + 1 lists and walking it downwards gives an O(n) solution with no comparisons at all. Offering the linear-time bucket variant unprompted is a strong signal, because it shows you noticed a property of the data rather than reaching for the structure the problem seemed to be about.

The same idea, restated as a median

Streaming median is the other place partial order earns its keep, and it is worth having ready because the follow-up is almost automatic. Split the values into a lower half under a max-heap and an upper half under a min-heap, and keep the sizes within one of each other. The two roots are then the values adjacent to the middle.

PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> upper = new PriorityQueue<>();

void add(int x) {
    lower.offer(x);
    upper.offer(lower.poll());                       // route through lower so the split stays correct
    if (upper.size() > lower.size()) lower.offer(upper.poll());
}

double median() {                                    // invariant: lower.size() == upper.size() or one more
    return lower.size() > upper.size()
            ? lower.peek()
            : (lower.peek() + upper.peek()) / 2.0;
}

Pushing every value through lower before rebalancing is what removes the comparison branch that most buggy versions contain: it guarantees the element lands on the correct side regardless of its magnitude. Insertion is O(log n), reading the median is O(1), and no element is ever compared against the far half of the data - which is the point of the whole family.