Heaps & Top-K
Keep the best candidate on top without ever fully sorting.
5 lessons · ~49 min · free
By the end you can
- Read a heap as a tree living inside an array
- Understand sift-up and sift-down, and why both are O(log n)
- Keep the top k of anything with a size-k heap of the opposite kind
- Merge k sorted sequences by racing their heads in a heap
- Decide between sorting, heaps, and quickselect from the constraints
Lessons
- 1Always know the minimum9 minThe priority queue promise, the tree hiding in an array, and what heapq actually guarantees.
- 2Sift up, sift down10 minHow a heap repairs itself after an insert or a pop, and why the cost is the tree's height.
- 3The top-k pattern11 minWhy a MIN-heap of size k finds the k LARGEST items, and the n log k win over sorting.
- 4Merging k sorted streams11 minRace the head of every list in one heap: merge k sorted lists, plus the two-heap median idea.
- 5Spotting heap problems8 minK-th, top-k, and streaming cues; heapq's max-heap workaround; when sorting is simply better.
Practice it after
Real interview questions that test this pattern, in an editor with execution and AI feedback.