Heaps and Top-K

1The mental model (what this really is)#

A heap is a container that always knows its most extreme element. That is the whole idea.

• Under the hood it is a complete binary tree packed into an array, where each parent beats its children by the heap's rule.
• A min-heap keeps the smallest thing on top. A max-heap keeps the largest thing on top.
• Peek at the top in O(1). Pull it out in O(log n). Push a new item in O(log n).
• You do not get a sorted list for free. You get exactly one guarantee: the top is always the extreme.

That single guarantee is weirdly powerful:

• Most "give me the biggest K," "smallest K," or "the median as numbers stream in" problems do not need full order.
• Full order costs O(n log n).
• The extreme, pulled repeatedly and cheaply, is all these problems ask for, and the heap sells it at O(log n) a pull.

Here is how that plays out in your head on every element:

• New number bigger than the top? Kick the top out, push the new one in.
• New number smaller than the top? It can never be in the final K, so drop it on the floor.
• The heap floats the current weakest survivor to the top so you can evict it in O(log K).

2How to recognize it (the signals in a problem)#

Train your ear for these phrases. When you hear them, your hand should already be moving toward a heap.

The literal tells.

• "K largest / K smallest / K closest / K most frequent"
• "Top K ..." anything
• "The Kth largest" (singular, still a heap problem)
• "Median of a data stream" or "running median"
• "Merge K sorted lists/arrays"
• "Schedule tasks by priority," or anything where priority changes as you go
• "Process events in order" when the order is dynamic, not fixed up front

The subtler tell: a stream, or huge data with a small slice wanted.

• "A billion numbers, give me the top 100" is the interviewer begging you not to sort.
• Sorting is O(n log n) and needs all the data in memory at once.
• A size-K heap is O(n log K) and needs only K items in memory.
• For K=100 and n=1e9: sorting does roughly 30 billion comparisons and asks for gigabytes of RAM; the heap does about 7 billion and holds 100 numbers.
• Say that out loud and watch the interviewer relax.

The third tell: "the next most extreme thing," repeatedly, from a set that keeps changing.

• Dijkstra, Prim, event simulation, any greedy-by-priority algorithm.
• That is a priority queue, which is a heap wearing a nicer name on its badge.

3The template (how it works, with pseudocode)#

Here is the Top-K-largest template. Memorize the shape, not the syntax.

function topKLargest(nums, k):
    min_heap = []                 # size will be capped at k
    for x in nums:
        push(min_heap, x)
        if size(min_heap) > k:
            pop(min_heap)         # removes the smallest -> the weakest survivor
    return min_heap               # the k largest, in no particular order

Why this exact shape.

• Walk every element once. Keep the heap capped at K. Whatever survives is your answer.
• Note the order: push first, then pop if you overflowed.
• The other way (check, then conditionally push) works too, but it forces a compare-against-top branch that is easier to get wrong under pressure.
• Push-then-trim is harder to break.

The quick variations off this same template.

• K-smallest: flip it. Use a max-heap of size K, and pop the largest when you overflow.
• Top K frequent: do a counting pass first, then run this same template over (count, item) pairs, comparing on count.

The priority-queue variant looks different but is the same tool:

function processByPriority(start):
    pq = [start]
    while pq not empty:
        item = pop(pq)            # the current most-extreme item
        for next in neighbors(item):
            if worth_doing(next):
                push(pq, next)

• Dijkstra, A*, "merge K sorted lists," task scheduling. All this shape.
• The only thing that changes between them is what "most extreme" means and what worth_doing checks.

4A worked example (walk through one problem step by step)#

The problem.

• Given nums = [3, 2, 1, 5, 6, 4] and k = 2, return the 2nd largest element.
• Classic "Kth largest in an array."

Name the baseline first, then beat it.

• The lazy answer is sort descending and index into position K-1. That works, it is O(n log n).
• In a real interview I say it out loud so the interviewer knows I see it.
• Then I say "but I can do better on space and on time if K is small," and I do.
• I keep a min-heap of size 2. Once I have seen everything, the top is exactly the 2nd largest, because the heap holds the 2 largest and the top is the smaller of those two.

Let me trace it.

• Start: heap [].
• See 3. Push. Heap [3]. Size 1, under the cap, leave it.
• See 2. Push. Heap [2, 3] (min on top is 2). Size 2, at the cap, fine.
• See 1. Push. Heap now holds {1, 2, 3}, size 3, over the cap. Pop the min, which is 1. Heap holds {2, 3}, top is 2.
• See 5. Push. Holds {2, 3, 5}, over cap. Pop min 2. Holds {3, 5}, top 3.
• See 6. Push. Holds {3, 5, 6}, over cap. Pop min 3. Holds {5, 6}, top 5.
• See 4. Push. Holds {4, 5, 6}, over cap. Pop min 4. Holds {5, 6}, top 5.

Done. Heap holds {5, 6}, the top is 5. The 2nd largest is 5. Correct.

What actually happened.

• The heap never grew past 2 items except for the brief instant during a push before the trim.
• Each push/pop was O(log 2), basically a single compare, basically free.
• We touched 6 numbers once each. Total work is O(n log k). Memory is O(k), not O(n).

Now scale it in your head.

• If nums were a stream of ten million numbers and k were 10, this exact code does not change one line.
• It holds 10 numbers and streams the other 9,999,990 straight through without ever storing them.
• Sorting cannot do that. It has to see all ten million at once.
• That is the answer that gets a nod, and it is the whole reason the pattern exists.

5Variations and gotchas#

Kth largest vs K largest. Same heap.

• For the single Kth value, return the top.
• For the list of K, return the whole heap (order inside is undefined, so sort it at the end if they want it sorted).
• Do not overthink it.

Top K frequent elements.

• Count with a hash map first, O(n).
• Then run the size-K min-heap over the entries, comparing on frequency, O(n log k).
• There is also a bucket-sort trick: index buckets by frequency from 1 to n, drop each element into its count's bucket, then read buckets from the top. That hits O(n) flat and is worth mentioning if they push you past the heap solution.

K closest points to origin.

• Same template, your comparison key is distance squared, x*x + y*y.
• Do not take the square root. You only need relative order, and sqrt just burns cycles and invites floating-point ties on points that are actually equidistant.

Merge K sorted lists.

• Put the head of each list into a min-heap.
• Pop the smallest, append it to output, push that node's successor.
• The heap only ever holds K items, one per list. O(N log K) for N total nodes, versus O(N log N) if you naively concatenated and sorted.
• Watch the tie case: pushing tuples where the second element is a non-comparable node will crash, so carry a tiebreaker index.

Median from a data stream. The elegant one.

• Keep two heaps: a max-heap for the lower half, a min-heap for the upper half.
• Keep their sizes balanced within one.
• The median is either the top of the bigger heap, or the average of the two tops when sizes are equal.
• The standard clean move on each insert: push to one heap, pop its extreme and push that into the other, then rebalance by size.
• People fumble the rebalancing direction, so practice it until it is muscle memory.
• Each insert is O(log n), each median read is O(1).

Heapify beats K pushes.

• If you have all the data up front and want a heap of everything, building it in one heapify pass is O(n), not the O(n log n) you would pay for n separate pushes.
• Different situation from the streaming size-K cap, but good to know and good to name.

Gotchas that bite.

• Picking a max-heap when you want K largest. Wrong tool. You will evict your best elements and keep the junk. It is min-heap for largest.
• Forgetting the size cap, so the heap grows to n and you have thrown away the whole point. O(n log n) with extra steps.
• In Python, forgetting to negate consistently when faking a max-heap. Negate on push and negate again on read, or your signs rot halfway through.
• Tuple comparisons in Python heaps exploding when the primary keys tie and the secondary object is not comparable. Add a monotonic tiebreaker counter as the middle field: (key, counter, obj).

6Complexity#

For the size-K heap over n elements:

• Time: O(n log k). Each of n elements triggers at most one push and one pop, each O(log k). It is log k, not log n, because the heap never exceeds k items.
• Space: O(k). Only the heap, regardless of how big n is.

Compare the alternatives so you can speak to trade-offs, because the trade-off conversation is half of what this question tests.

• Full sort then slice: O(n log n) time, O(n) space (or O(1) extra if sorting in place). Fine for small n, wasteful for large n with small k, impossible for an unbounded stream.
• Rule of thumb I say out loud: streaming or huge-n-small-k, reach for the heap at O(n log k). All data in memory and they want raw average speed, name quickselect at O(n). Small input, just sort and move on.

7Mistakes that cost people the round#

The backwards heap. Max-heap for K largest.

• This is the number one error, and I see it weekly.
• Say the rule out loud as you code: "K largest means min-heap of size K, so I can evict the weakest."
• It cements it for you and shows the interviewer you understand why, not that you memorized a snippet.

Sorting when you were handed a stream.

• If the problem says "as numbers arrive" and you ask to sort, you have missed the entire point, and the interviewer now doubts you can reason about memory.
• The word "stream" is a flashing sign that reads "do not hold all the data."

Not capping the heap.

• A heap that grows to size n gives you O(n log n), the same as sorting, with more code and more bugs.
• If your heap is not capped at K, stop and ask yourself why you are using one at all.

Square-rooting distances.

• In K-closest-points, comparing squared distances is enough.
• Taking sqrt is slower and risks float ties on equidistant points.
• Small thing, but a sharp interviewer notices, and the small things are how two "passing" candidates get ranked against each other.

Mumbling the complexity.

• Say "O(n log k) time, O(k) space" clearly and explain why k and not n.
• The complexity story is the reason this pattern exists. If you cannot articulate it, they will assume you pattern-matched the code without understanding it.

Ignoring the quickselect option entirely.

• For an in-memory Kth-largest, a strong candidate names quickselect and its O(n) average up front.
• You do not have to code it, but knowing it exists and when it beats the heap separates you from the pack.

The cap is the pattern. Drop the cap and you are just sorting with a fancier name.

8Your practice path (named problems by difficulty)#

Do these in order. Do not skip the Easy ones. They build the reflex that fires in the first thirty seconds.

Warm-up / Easy.

• Kth Largest Element in a Stream
• Last Stone Weight

Core / Medium (this is the meat, do all of them).

• Kth Largest Element in an Array
• Top K Frequent Elements
• K Closest Points to Origin
• Sort Characters by Frequency
• Task Scheduler
• Reorganize String

Stream and merge.

• Merge K Sorted Lists
• Find K Pairs with Smallest Sums
• Smallest Range Covering Elements from K Lists

Boss level / Hard.

• Find Median from Data Stream
• Sliding Window Median
• IPO (maximize capital, two-heap greedy)

9Where this shows up#

• Amazon: "top N products / sellers / frequent items" is almost its own genre, and it ties straight into Customer Obsession stories.
• Google and Meta: the stream and median variants, plus priority-queue-driven graph problems like Dijkstra dressed up as "cheapest path with weird costs."
• Microsoft and the trading firms (Jane Street, Citadel, Two Sigma): "merge K sorted" and real-time priority scheduling, since both map onto order-book and event-loop work they do for real.
• System design rounds: the same idea resurfaces as "leaderboard," "trending topics," or "top-K by count" over a firehose of events, usually paired with approximate structures like Count-Min Sketch once exact counts over billions of events get too expensive to keep.

Want to know which of these shows up most in the company you are targeting? Check the company guides to see where this pattern lands in each interview loop.