Search Target: 15s
Heap is better than sorting when k << n. Quickselect is O(n) average but doesn't order results.
HEAP vs SORTING FOR TOP-K
─────────────────────────
SORTING:
sorted(a)[-k:] # O(n log n) time, O(n) space
+ Simple code
+ Get all elements in order
- Must process all elements upfront
MIN-HEAP of size k:
import heapq
heapq.nlargest(k, a) # O(n log k) time, O(k) space
+ Better when k << n
+ Can process stream (online)
+ O(k) space
MAX-HEAP (negate values):
heap = [-x for x in a]
heapq.heapify(heap) # O(n)
top = -heapq.heappop(heap)
QUICKSELECT:
O(n) average for kth element
+ Fastest average case
- O(n²) worst case
- Doesn't sort the top k
DECISION:
k close to n? → just sort
k << n? → min-heap of size k
Only need kth value? → quickselect
Stream of elements? → heap (must be online)Type it from memory. Go.