Heap / Priority Queue
Top K, two heaps, scheduling and k-way merge.
4 notes · 22 min total
Questions0 of 28 done
Warm up with these before Phase 1.
Patterns
- 1Heap Basics & Top KHow heapq works, the negation trick for max-heaps, and why a size-k heap finds the top K in O(N log K).7 min
- 2Two HeapsSplit a stream into a small half and a large half with two heaps, so the median (or the split point) is always at the tops.4 min
- 3Scheduling & Greedy with RegretUse a heap to always act on the best option now, a queue to park items until they're ready, and a heap to undo your worst past choice.7 min
- 4K-Way MergeMerge K sorted sources by keeping only each source's current head in a min-heap, and use it for Kth-smallest and K-pairs problems.4 min