Why must a size-k heap that keeps the k largest values be a min-heap rather than a max-heap?
answer
- Think about what gets thrown away
- Which of the k survivors leaves first?
- Cheap access is needed to the weakest kept
- The root is the bar a newcomer beats
- Root ends up as the kth largest
basics
~20 sThe heap must be a min-heap because its root is the smallest of the k values you are still keeping — the bar a new value must beat. A max-heap would evict the largest values and leave you the k smallest.
solid answer
~50 sThe size-k heap holds survivors, not candidates, so the element you need at your fingertips is the weakest one still inside — and that is the root of a `min-heap`. The rule is: fill the heap with the first k values, then for each new value compare it against the root; if it is larger, remove the root and insert the new value, otherwise discard it. That keeps the invariant "the heap contains exactly the k largest values seen so far" after every element. Flip the orientation and the guard evicts the root of a max-heap — the biggest value in the heap — so every strong value you meet is thrown away immediately and you finish holding the k smallest. As a bonus, after the whole pass the min-heap's root is the kth largest value overall.
go deeper
Be ready to say which orientation the size-k heap uses and why. The root has to be the weakest value you are still keeping, because that is what a newcomer must beat and who leaves when it wins.
Explain the invariant and the guard out loud: after every element the heap holds exactly the k largest seen so far, and a new value does any heap work only when it strictly beats the root.
Show what the choice costs in practice — bounded O(k) state, arbitrary tie-breaking at the bar, and a result that is a set rather than a ranked list until you spend another O(k log k).
Own the framing: this orientation is what converts an offline ranking into a bounded-memory single-pass computation, and it quietly fixes k before anyone has seen the data.
## The shape of the problem You are given values one at a time — readings coming off a sensor line, sizes, scores — and asked for the k largest of them, where k is much smaller than the number of values n. The classic answer is to carry a heap that never grows beyond k entries. The orientation of that heap is the single detail candidates get backwards most often, because the phrase "k **largest**" pulls the mind toward "**max**-heap". ## The heap holds survivors, not candidates The fix is to notice what the heap is actually for. It is not a ranking of the values you have seen; it is the set of values that are still in the running, and its only job is to answer one question cheaply: *which member of this set is the weakest, so I know what a newcomer has to beat, and so I know who leaves when a newcomer wins?* A heap gives cheap access to exactly one extreme — its root. So the root must be the **weakest survivor**, which means the heap must be ordered so that the smallest value sits on top: a min-heap. ## The invariant and the guard The loop is three lines of logic and one invariant. - Invariant: *after processing the first i values, the heap contains exactly the k largest of them* (all i of them, while i < k). - Fill: while the heap holds fewer than k values, insert unconditionally. - Guard: once it holds k, compare the new value x against the root. If `x > root`, remove the root and insert x. Otherwise discard x — it cannot be among the k largest, because k values already beat it. Each retained value costs one removal plus one insertion, both O(log k); each rejected value costs a single comparison. Space is O(k) and the pass is one-directional, so the input can be a stream whose length you do not know. ## Traced on a short stream Take readings 12, 45, 7, 88, 30, 91, 5 with k = 3, heap shown root-first. | arriving | heap before | action | heap after | |---|---|---|---| | 12 | {} | fill | {12} | | 45 | {12} | fill | {12, 45} | | 7 | {12, 45} | fill | {7, 12, 45} | | 88 | {7, 12, 45} | 88 > 7, evict 7 | {12, 45, 88} | | 30 | {12, 45, 88} | 30 > 12, evict 12 | {30, 45, 88} | | 91 | {30, 45, 88} | 91 > 30, evict 30 | {45, 88, 91} | | 5 | {45, 88, 91} | 5 < 45, discard | {45, 88, 91} | Result: {45, 88, 91}, and the root 45 is the third-largest reading. ## The max-heap version, traced to its garbage Now run the same stream with a max-heap, evicting the root whenever the size exceeds 3. Filling gives {45, 12, 7} with root 45. 88 arrives, is inserted, becomes the root, and is evicted at once — the largest reading in the stream is gone on the step it appeared. 30 arrives, is inserted, and evicts 45. 91 arrives and is evicted immediately. 5 arrives, is inserted, and evicts 30. You finish holding {12, 7, 5}: the three *smallest* readings. That is not a near miss or a slower path to the right answer; it is the exact inverse of the requested result, and it is what makes this a favourite screening question. ## The mirror, and the boundaries For the k **smallest** values, mirror everything: a size-k **max**-heap whose root is the largest survivor, keeping a new value only when it is smaller than the root. Same invariant, same costs. Three boundaries are worth having ready: - **k = 1** degenerates to a running maximum — one comparison per value, constant space. A heap here is correct but pointless overhead. - **k >= n** means nothing is ever evicted; the heap ends up holding everything, and you have paid O(n log n) to get no advantage over sorting. - **Duplicates and ties at the bar** are broken arbitrarily. If several values equal the root, which copies survive depends on arrival order and on the heap's internal layout. The result is still a valid top-k multiset, but it is not reproducible run to run unless you add an explicit tiebreak key. ## What you get back, and in what order The heap gives the k largest as a *set*, not a sorted list — a heap is only partially ordered. If the output has to be ranked, drain the heap into a list and reverse it, or sort the k results: an extra O(k log k), negligible when k is small, and a step people forget to mention.
- After the full pass, what does the root of the size-k min-heap hold?The kth largest value in the whole input. Every value in the heap beats it and every discarded value lost to it, so it sits exactly at rank k. That is why the same structure answers "give me the kth largest" for free, with no extra work beyond reading the root.
- How do you adapt the same pattern to the k smallest values?Mirror it: use a size-k max-heap whose root is the largest survivor, and keep a new value only when it is smaller than the root. The invariant becomes "the heap holds the k smallest seen so far", and the costs are identical — O(log k) per retained value, O(k) space, one pass.
- What happens when many values tie at the boundary of the heap?The guard keeps a newcomer only when it strictly beats the root, so ties are discarded and the earliest arrivals win — but which equal copies are sitting in the heap depends on eviction order and internal layout. The multiset of results is correct; the specific copies are not reproducible unless you add a deterministic tiebreak key.
Think of a k-seat waiting room with a bouncer. The person the bouncer needs at their fingertips is the weakest guest already inside, because that is who leaves the moment someone better shows up.
saying these in an interview costs you the question
- Says k largest obviously means a max-heap
- Claims the root of the size-k heap is the maximum
- Evicts the maximum on overflow, keeping the k smallest
- Thinks the heap must hold all n values
- Assumes the k results come out already sorted