1Understand
The idea
To keep the k largest items, keep a min-heap of size k: its smallest element is the weakest of the current top k, so it is the one to evict when something better arrives. That is O(n log k) instead of sorting everything in O(n log n), and it works on a stream.
Intuition
To keep the k largest items, keep a min-heap of size k: its root is the weakest of the current champions, so that is the one to evict when something better arrives. That is O(n log k) and works on a stream, you never need all n items sorted.
For k smallest, use a max-heap (negate in Python). heapq.nlargest hides the same idea for offline arrays.
Sorting everything is O(n log n); when k ≪ n, the bounded heap wins.
What you will be able to do
- Choose min-heap vs max-heap (negate)
- Bound the heap at k
When to use it
- K largest / smallest / most frequent
- K closest points
- Stream where only the best k matter
2See it
Walkthrough
Top-k with a size-k min-heap
Keep the 2 largest from [5, 1, 9, 3]. Evict the weakest of the current top-k.
1 / 5
k = 2. Push 5. Heap holds the current top candidates; root is the smallest of them.
Live template
Complexity: time O(n log k), space O(k)
O(n log k) time, O(k) space. Full sort is O(n log n). Quickselect is expected O(n) offline but does not stream and has a worse worst case. Prefer the heap when k is small or data is streaming.
Read the walkthrough as text
Kth largest in a stream / array. nums = [3,2,1,5,6,4], k = 2 (find 2nd largest overall → 5).
- Push first k elements into a min-heap: after
[3,2]heap root is2. - For
1: smaller than root, ignore. - For
5: push and pop → heap holds[3,5]. - Continue; end heap root is
5, the kth largest.
In code:
import heapqh = nums[:k]heapq.heapify(h)for x in nums[k:]:if x > h[0]:heapq.heapreplace(h, x)return h[0]
3Recognise it
Kinds of problems (9)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
K largest / smallest
Example. Return k largest elements from an unsorted array.
How. Size-k min-heap keeps the k biggest seen; pop when length exceeds k.
K most frequent
Example. K most common elements.
How. Count frequencies, then size-k heap on (freq, value), min-heap on frequency.
K closest points
Example. K points nearest the origin.
How. Max-heap of size k by squared distance; farthest among k is evicted on overflow.
K-th largest in a stream
Example. Return k-th largest on each insert.
How. Maintain size-k min-heap; k-th largest is always heap root after balancing.
Task scheduling with a heap
Example. Schedule tasks with cooldown using ready/max-heap of frequencies.
How. Greedy pop most frequent ready task; push back after cooldown with updated count.
Greedy simulation with a max-heap (last stone, reorganise string)
Example. Repeatedly smash two largest stones or rearrange by frequency.
How. Max-heap drives each greedy step; push back reduced counts until done.
Sort by one key, heap over the other
Example. Two-key sorting: primary sort, secondary resolved by heap.
How. Sort rows by one field; per group maintain heap on the other key for top picks.
Allocate the smallest free resource
Example. Assign tasks to smallest available server id.
How. Min-heap of free server ids; pop on assign, push back after finish time with heapq.
Shrink a range with a heap (minimise deviation)
Example. Remove elements to minimise range, track extremes in a heap.
How. Sort or heap-aided removal: always drop current min or max to shrink spread greedily.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Wrong heap direction
Why it happens. Python heapq is a min-heap, so “largest k” needs negation, easy to forget.
How it fails. K largest kept in min-heap without negating, you evict the largest and keep small values.
Fix. K largest: min-heap size k on raw values. K smallest: max-heap via negate (or opposite).
Full sort
Why it happens. sort() is one line and always correct.
How it fails. n = 10⁶, k = 10: full O(n log n) sort blows time limit when O(n log k) heap suffices.
Fix. Maintain size-k heap during one pass, O(n log k) time, O(k) space.
Unbounded heap
Why it happens. Pushing everything then slicing k off the end still yields the answer.
How it fails. Heap length n uses O(n) memory and still does O(n log n) pops, misses the bounded structure.
Fix. After each push, if len(heap) > k: pop once so heap never exceeds k.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.