Heap vs Quickselect for Top-K: When O(n log K) Beats O(n)
- Heap runs O(n log K), works on streams, and never mutates the input — the default for small K or unbounded data.
- Quickselect runs O(n) on average in-place, but requires the full array and a randomized pivot to avoid O(n²) worst case.
- For small K (K ≤ log n), the heap's O(n log K) is practically O(n) and the safer, simpler choice.
- For large K (K ≈ n/2), quickselect clearly wins: the heap degrades to O(n log n) while quickselect stays O(n).
- Streams demand the heap: quickselect needs random access to the full dataset — it cannot run until the stream ends.
- Ask one clarifying question before coding: "Is the data a stream, or is the full array available?" It decides the algorithm.
std::nth_elementin C++ uses introselect, a quickselect variant with a median-of-medians fallback that guarantees O(n) worst case.
You have a million log entries. You want the 10 slowest requests. Your first instinct is probably to sort the whole thing and take the tail. That instinct is wrong, and it gets more wrong the larger K gets.
The two real contenders are a min-heap capped at size K, and quickselect partitioning down to the K-th boundary. Both beat sorting. They make opposite tradeoffs. Most engineers reach for the heap without thinking about the other option, which means they leave O(n) on the table every time K is large.
Sort() Is Doing Way Too Much
Sorting the full array and grabbing the last K elements costs O(n log n). That's correct, but it's like hiring a full orchestra to play Happy Birthday. You'll get it done. You'll also pay for 80 musicians who weren't needed.
You don't need a total order. You just need a boundary. Both heap and quickselect exploit this. Neither sorts the full array.
The universal instinct to just call .sort() and grab the tail. JavaScript will punish you especially hard for this one.
The Heap: A Rolling Window of the Best K
Keep a min-heap of exactly K elements. For every new element, if it's larger than the smallest thing already in the heap, evict that minimum and insert the new element.
import heapq def top_k_heap(nums: list[int], k: int) -> list[int]: min_heap: list[int] = [] for num in nums: heapq.heappush(min_heap, num) if len(min_heap) > k: heapq.heappop(min_heap) return min_heap # unsorted; call sorted() if order matters
Walk through it on a concrete input:
nums = [3, 1, 4, 1, 5, 9, 2, 6] K = 3
Target: the 3 largest
Process 3: heap=[3]
Process 1: heap=[1, 3]
Process 4: heap=[1, 3, 4] ← full, min=1
Process 1: 1 ≤ min(1), skip
Process 5: 5 > min(1), pop 1, push 5 → heap=[3, 4, 5]
Process 9: 9 > min(3), pop 3, push 9 → heap=[4, 5, 9]
Process 2: 2 ≤ min(4), skip
Process 6: 6 > min(4), pop 4, push 6 → heap=[5, 6, 9]
Result: {5, 6, 9} ✓
Why It's O(n log K)
Each element triggers at most one push and one pop, both O(log K) on a heap of size K. With n elements: O(n log K). Space is O(K) for the heap.
When K is small, log K is tiny. For n = 1,000,000 and K = 10, log K ≈ 3.3 compared to log n ≈ 20. You're doing about 6x fewer comparisons than a full sort. That's why the heap feels so good for small K. It genuinely is that good.
Quickselect: Stop When You Hit the Boundary
Quickselect is quicksort with the self-restraint to stop early. It only recurses into the one partition that contains your target index.
After one partition pass, the pivot is at its final sorted position. If that position is exactly n-K, you're done. Every element to its right is already in the top K, unsorted.
import random def top_k_quickselect(nums: list[int], k: int) -> list[int]: target = len(nums) - k # want elements at indices [target, n-1] def partition(left: int, right: int) -> int: pivot_idx = random.randint(left, right) nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] pivot = nums[right] store = left for i in range(left, right): if nums[i] <= pivot: nums[store], nums[i] = nums[i], nums[store] store += 1 nums[store], nums[right] = nums[right], nums[store] return store left, right = 0, len(nums) - 1 while left < right: p = partition(left, right) if p == target: break elif p < target: left = p + 1 else: right = p - 1 return nums[target:] # top K, unsorted
On the same input:
nums = [3, 1, 4, 1, 5, 9, 2, 6] K = 3
target index = 8 - 3 = 5
Round 1: pivot = 4, partition around it
After: [1, 1, 2, 3, | 4 | , 9, 5, 6] pivot lands at index 4
target=5 > 4, so search right half: indices [5, 7]
Round 2: subarray [9, 5, 6], pivot = 6
After: [5, | 6 | , 9] pivot lands at index 6 (globally)
target=5 < 6, so search left: indices [5, 5]
Single element at index 5 → that's our boundary.
nums[5:] = [5, 6, 9] ✓ (unsorted within this slice)
Why It's O(n) on Average
Each pass scans the current subarray and cuts it roughly in half. Expected work:
n + n/2 + n/4 + n/8 + ... = 2n → O(n)
Formally: T(n) = T(n/2) + O(n), which by the Master Theorem gives O(n).
With randomized pivot selection, worst case (O(n²)) happens with negligible probability. The standard library std::nth_element in C++ uses introselect, a hybrid that falls back to median-of-medians to guarantee O(n) worst case.
Head to Head
| Property | Min-Heap | Quickselect |
|---|---|---|
| Time average | O(n log K) | O(n) |
| Time worst case | O(n log K) | O(n²) with bad pivots |
| Space | O(K) | O(1) extra (O(log n) stack) |
| Works on streams? | Yes | No |
| Modifies input? | No | Yes (in-place) |
| Returns sorted K? | No (heap order) | No (partition order) |
| Stable? | No | No |
When the Heap Is the Right Call
Use the heap when data arrives incrementally or you can't hold everything in memory.
A heap processes elements one at a time. You can feed it from a file, a network socket, or a generator and always know the current top-K. Quickselect requires random access to the full array. It literally cannot start until the stream ends.
Stream: 8, 3, 7, 1, 9, 2, ...
Heap maintains top-3 after every element.
Quickselect cannot run until the stream ends.
The heap also wins when K is tiny. If K = 1, each heap operation is O(1), and you scan the array in O(n) with zero overhead. Quickselect still does multiple partition passes.
Any time K ≤ log n, the heap's O(n log K) is practically O(n) and it's the safer choice.
When Quickselect Pulls Away
Use quickselect when you have the full array, K is large, and you want the lowest constant factor.
The crossover happens around K = n/2. At that point, the heap is O(n log(n/2)) = O(n log n), while quickselect stays O(n). For finding the median of a million-element array, quickselect is the standard approach. The heap doesn't have an answer for this.
n = 10,000 K = 5,000
Heap: O(n log K) = O(10,000 × 13) = ~130,000 ops
Quickselect: O(n) = O(10,000 × 2) = ~20,000 ops (avg 2n)
Quickselect also wins when memory is constrained. The heap holds K elements in RAM. If K is large, that matters. Quickselect does its work in-place.
In C++, std::nth_element is essentially introselect (quickselect with median-of-medians fallback). It's the idiomatic top-K for offline problems in performance-critical code.
Here's the full picture as K grows:
As K grows from 1 → n:
K=1 K=10 K=n/2 K=n
| | | |
Heap: O(n·0) O(n·3.3) O(n·log n/2) O(n log n)
QS: O(n) O(n) O(n) O(n)
↑ ↑
identical QS breaks away
The heap is asymptotically better only when K is small relative to n. For large K, quickselect's O(n) average is unbeatable.
LeetCode 215: Which One Do You Reach For?
LeetCode 215 (Kth Largest Element in an Array) is the canonical version of this problem. Which approach the interviewer wants depends entirely on one thing you should ask before writing any code.
If they mention a data stream or "continuously updating data," reach for the heap. That's the pattern from min-heap for top-K.
If they hand you a static array and ask for optimal time complexity, quickselect is the answer. Explain the O(n) average, mention the O(n²) worst case, and note that randomized pivot selection makes that worst case astronomically unlikely. If they push on worst-case guarantees, bring up median-of-medians or introselect.
Either way, the first thing out of your mouth should be: "Is this a stream, or is the full array available?"
That one question determines the algorithm. And the interviewer is watching to see if you ask it.
Four Ways Candidates Blow This
Building heap sort instead of a top-K heap. The heap should stay at size K throughout. Some candidates build a full n-element heap and then pop K times: that's O(n + K log n), worse than both approaches for large n. The heap evicts elements as it grows past K. It never gets bigger.
Forgetting that quickselect modifies the array. In interviews, say this upfront. If the caller can't tolerate mutation, you either copy first (O(n) space) or use the heap instead.
Treating O(n log K) as always better. When K = n/2, log K = log(n/2) ≈ log n. You're paying O(n log n). Quickselect's O(n) average clearly wins. The comparison only favors the heap when K is small.
Not randomizing the pivot. A naive quickselect that always picks the last element is O(n²) on sorted input. One line of randomization fixes this. Most candidates skip it.
The energy of building a full heap when K is 500,000 and n is 1,000,001.
What These Problems Are Actually Testing
Both algorithms come up in more contexts than just "find top K": closest K points to origin, K most frequent elements, top K salaries. The heap generalizes naturally to custom comparators. Quickselect generalizes to any partition criterion.
The harder skill isn't implementing either one from memory. It's recognizing which constraint makes the decision for you, then explaining that reasoning out loud before writing a single line. If you want to practice exactly that, SpaceComplexity runs voice-based mock interviews where you narrate your approach before you touch the keyboard. That's the skill these problems test.
The Rule
- Heap: O(n log K), works on streams, safe worst case. Best when K is small or data is unbounded.
- Quickselect: O(n) average, in-place, no stream support. Best for large K on a static array.
- Crossover point: around K = log n the heap matches quickselect in practice; around K = n/2 quickselect pulls clearly ahead.
- Always ask if the input is a stream. That single question determines the algorithm.
- Randomize the pivot. Non-randomized quickselect is O(n²) on sorted inputs.
std::nth_element(C++) uses introselect, a hybrid that guarantees O(n) worst case.