K-th Largest Element
Find the k-th largest element using a min-heap of size k: add each element, pop the min when heap exceeds k. After processing all elements, the root is the k-th largest.
K-th largest = a VIP club with only k seats. The bouncer (min-heap root) is the weakest VIP. New arrivals only get in if they're stronger than the bouncer, who then gets kicked out. The bouncer is always your answer.
Min-heap of size k: O(n log k) time, O(k) space. Quickselect: average O(n), worst O(n²), O(1) extra space. Sorting: O(n log n). For streaming data (online k-th largest), the min-heap approach is the only one that works. For static arrays, quickselect is faster on average. BFPRT (median-of-medians) gives guaranteed O(n) worst case for k-th smallest.
Quickselect correctness: after partition, pivot is at its final sorted position p. If p == k-1, done. If p < k-1, recurse right. If p > k-1, recurse left. Average case: expected partitions hit O(n) total work (geometric series: n + n/2 + n/4 + ... = 2n). Worst case O(n²) with bad pivots — use random pivot. Median-of-medians guarantees pivot within the middle 30-70% of values — reduces to T(n) = T(n/5) + T(7n/10) + O(n) which solves to O(n) by master theorem. In practice, quickselect with random pivot is preferred due to better constants.
For k-th largest in a stream or when memory is limited, I use a min-heap of size k — O(n log k) time, O(k) space, and easily handles new elements arriving. For a static array where k is small, quickselect gives O(n) average. I mention both trade-offs: heap is O(n log k) but online and space-efficient; quickselect is faster but offline and mutates the input. If the interviewer asks about guaranteed O(n), I mention median-of-medians but note that the constant factor makes quickselect with random pivot faster in practice.
Using a MAX-heap of size k instead of a MIN-heap of size k gives wrong results — you want the min of the top-k elements (the k-th largest) to be at the root. A max-heap of size k keeps the k largest seen so far but has the largest (not k-th largest) at the root. Keep the min-heap: the root IS the k-th largest answer.