Min-Heap vs Sorting for Top-K: When O(n log K) Beats O(n log n)
- Min-heap of size K runs in O(n log K) — up to 9x fewer comparisons than O(n log n) sorting when K is tiny relative to n.
- Use a top-K elements heap when K << n or data streams: each element costs O(log K) and only K items ever sit in memory.
- Use sort when K ≈ n, sorted output is required, or n is small enough that constant factors dominate.
- Heapify + K pops is O(n + K log n) — faster than the streaming heap approach when the full array is available upfront.
- Quickselect finds a single order statistic in O(n) average time but does not return the full top-K set.
- Python's negation trick (
-value) converts a min-heap into a max-heap, the standard pattern for K-smallest problems. - Two questions decide every top-K problem: is the data streaming, and how large is K relative to n?
Every coding interview eventually gives you a top-K problem. Find the K largest elements. Return the K most frequent words. The K closest points to the origin. Same shape, dozens of variations, one question underneath all of them: are you going to sort a million things to find five of them?
Two approaches dominate: sort everything and slice, or maintain a bounded min-heap. Both are correct. One is meaningfully faster when K is small. Knowing which to reach for, and being able to explain why, is what separates a good answer from a strong hire.
What You're Actually Trying to Do
Say you have an array of n numbers and want the K largest. The natural instinct is to sort descending and take the first K. That works. It also does a lot of unnecessary work that your interviewer is quietly judging you for.
The heap approach asks a different question: instead of ordering all n elements, can you track only the top K candidates as you scan? Yes. A min-heap of size K does exactly that. The smallest element in the heap is always the weakest candidate in your current top-K set. Think of it as a bouncer with a capacity limit. Every new element either gets turned away or bumps out the weakest current occupant.
Min-heap of size K=3, finding top-3 from [3, 1, 5, 6, 2, 4]:
Process 3: heap = [3]
Process 1: heap = [1, 3]
Process 5: heap = [1, 3, 5]
Process 6: 6 > heap[0]=1 → pop 1, push 6 → [3, 5, 6]
Process 2: 2 < heap[0]=3 → skip
Process 4: 4 > heap[0]=3 → pop 3, push 4 → [4, 5, 6]
Result: {4, 5, 6}
The heap's minimum is the "weakest" element you're willing to keep. Every new element competes against it. If it wins, it gets in and bumps the bottom.
Sort First (The Comfortable Lie)
def top_k_sorting(nums: list[int], k: int) -> list[int]: return sorted(nums, reverse=True)[:k]
Three characters. Readable. Passes every test case. Gets the job done. Also costs O(n log n) regardless of what K actually is.
That's the problem. If n = 1,000,000 and K = 5, you're running a full sort on a million elements to retrieve five of them. Every comparison, every swap, every memory operation spent on the 999,995 elements you are about to throw away. It's like hiring a moving company to carry one box.
Track Top-K With a Heap
import heapq def top_k_heap(nums: list[int], k: int) -> list[int]: heap: list[int] = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return sorted(heap, reverse=True) # Or just use the built-in directly: heapq.nlargest(k, nums) # same O(n log k) complexity
Each element touches the heap at most once (push, then a conditional pop). A push/pop on a heap of size K costs O(log K). Total: O(n log K) time, O(K) space.
The Numbers: When Does the Gap Actually Matter?
The two complexities differ by exactly one factor: log n vs log K. In absolute terms:
| K | n = 1,000,000 | log₂ n | log₂ K | Speedup (approx) |
|---|---|---|---|---|
| 5 | 1,000,000 | 20 | 2.3 | 8.7x fewer comparisons |
| 100 | 1,000,000 | 20 | 6.6 | 3x fewer comparisons |
| 1,000 | 1,000,000 | 20 | 10 | 2x fewer comparisons |
| 100,000 | 1,000,000 | 20 | 17 | 1.2x fewer comparisons |
| 500,000 | 1,000,000 | 20 | 19 | ~same |
When K is 0.1% of n, the heap makes nearly 9x fewer comparisons. When K is half of n, the gap collapses to noise.
Python's standard library internalizes exactly this. The heapq source for nlargest and nsmallest automatically falls back to sorted() when K exceeds roughly half of n. You get the optimal behavior for free. Understanding why is what makes your answer interview-ready.
There Are Actually Four Approaches
Before the examples, one clarification: if you only need the Kth largest element (a single value, not the top-K set), quickselect runs in O(n) average time and O(1) space. Quickselect is a partition-based algorithm that splits around a pivot and recurses only into the relevant half. Average O(n), worst-case O(n²) on adversarial inputs. It doesn't return a sorted list and it doesn't handle streaming data.
A fourth option worth knowing: heapify the full array in O(n) time (not O(n log n)), then pop K times at O(log n) each. Total: O(n + K log n). Faster than the streaming heap when you have the whole array and K is moderate.
| Approach | Time | Space | Streaming? | Sorted output? |
|---|---|---|---|---|
| Sort + slice | O(n log n) | O(n) | No | Yes |
| Min-heap size K | O(n log K) | O(K) | Yes | No |
| Heapify + K pops | O(n + K log n) | O(n) | No | No |
| Quickselect | O(n) avg, O(n²) worst | O(1) | No | No (one element only) |
Worked Example 1: Kth Largest Element (LeetCode 215)
Find the Kth largest element in an unsorted array. The heap approach turns a potential O(n log n) sort into O(n log K).
import heapq def find_kth_largest(nums: list[int], k: int) -> int: heap: list[int] = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap[0] # smallest in the top-K heap = Kth largest
heap[0] at the end is the Kth largest. Every smaller element got evicted. The heap root is the cutoff, which is exactly the element you want.
Worked Example 2: Top K Frequent Elements (LeetCode 347)
Return the K most frequent elements from an array.
from collections import Counter import heapq def top_k_frequent(nums: list[int], k: int) -> list[int]: count = Counter(nums) return heapq.nlargest(k, count.keys(), key=count.get)
The heap operates over unique elements, not the raw array. If your input has 1,000,000 numbers but only 500 distinct values, n in the complexity analysis becomes 500. The heap advantage compounds: small K, small effective n.
An alternative worth knowing: bucket sort by frequency gives O(n) time and O(n) space. If K ≈ n/2 and the frequency distribution is bounded, bucket sort wins.
Worked Example 3: K Closest Points to Origin (LeetCode 973)
Return the K closest points to (0, 0) from a list of 2D points.
You want K smallest distances, so you need a max-heap of size K. Python only has a min-heap, so you negate.
import heapq def k_closest(points: list[list[int]], k: int) -> list[list[int]]: heap: list[tuple[int, list[int]]] = [] for x, y in points: dist = -(x * x + y * y) # negate: min-heap of negatives = max-heap heapq.heappush(heap, (dist, [x, y])) if len(heap) > k: heapq.heappop(heap) return [point for _, point in heap]
The negation trick is standard Python for any top-K minimum problem. Negate on push, negate back on retrieval. It looks cursed the first time. It becomes muscle memory.
Also notice: we store distance squared, not distance. Since we're only comparing, we skip the square root entirely. Free O(1) savings on every single one of the n comparisons.
When Sorting Wins Back
The heap's advantage collapses in three situations. No shame in reaching for sorted().
K is large. If K = n/2, sorting does O(n log n) and the heap does O(n log(n/2)) = O(n(log n - 1)) ≈ O(n log n). The gap becomes rounding error. Sort for simplicity. The heap vs sorted array tradeoff shifts entirely based on this ratio.
You need sorted output. A heap returns K elements in arbitrary order. If they need to be ranked, you need an O(K log K) sort on the result. For small K this is negligible. For large K, you've effectively paid for two passes.
Tiny arrays. If n < 100, none of this matters. sorted() has lower constant factors and no per-element branching overhead. The sort completes so fast that complexity analysis is a moot point. Write the readable version and move on.
Streaming Data: Where Heap Is the Only Option
Sorting requires the full array in memory upfront. A heap doesn't.
Imagine processing a live stream of user scores to maintain a top-100 leaderboard. You can't sort what you haven't seen yet. The heap handles this naturally: each new score costs O(log K) to process, the heap uses O(K) memory, and at any moment you have the current top-K.
This is where O(K) space starts to look genuinely impressive rather than just academically interesting. If the stream is effectively infinite and K = 100, you're holding exactly 100 numbers in memory regardless of how many billions of scores you've processed. The heap size is a constant. The stream is not your problem.
For recognizing when a problem wants this pattern, Top-K Elements All Look Different. The Heap Signal Isn't. covers the structural clues in problem statements that indicate a bounded heap.
Why Is Push/Pop O(log K)?
A heap is a complete binary tree stored as an array. Push adds to the end and bubbles up; pop removes the root and bubbles down. Height is log K, so each operation touches at most log K nodes. The Min-Heap: What It Is and Why Interviews Love It has the full proof, including why heapify is O(n) and not the O(n log n) you might expect.
Two Questions, Same Answer Every Time
When you see a top-K problem in an interview, two questions determine your approach:
- Is the data streaming, or is the full array available? Streaming means heap. No choice.
- How large is K relative to n? K << n means heap wins. K ≈ n means sort. K = 1 or K = n-1 can sometimes be handled with a single linear scan.
The common mistake is defaulting to sorted() because it's one line. That's fine in production code for small n. In an interview, stating the complexity trade-off before reaching for sorted shows you understand both tools. The interviewer isn't just watching you solve the problem. They're watching how you reason about the space between approaches.
If you want to practice explaining those trade-offs out loud under real conditions, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly this kind of reasoning. It's a different muscle than grinding LeetCode silently.
The Short Version
- Min-heap of size K: O(n log K) time, O(K) space. Use when K << n or data is streaming.
- Sort + slice: O(n log n) time, O(n) space. Use when K ≈ n, you need sorted output, or simplicity matters more.
- Heapify + K pops: O(n + K log n). Faster than the streaming approach when the full array is available.
- Quickselect: O(n) average for finding one order statistic, not a set.
- The negation trick (
-value) turns Python's min-heap into a max-heap. Required for K-smallest problems. Looks weird. Works every time.