Lesson 13: Heaps & top-K
Picture a hospital ER: patients aren't treated by arrival order, but by urgency. The structure that does exactly this is a 'heap' — a priority queue that always gives fast access to the extreme item (smallest or largest). In Python: heapq, with insert/remove at O(log n). It's the natural tool for 't
A heap is like a hospital queue that always pulls the next most urgent patient. In Python's heapq, 'most urgent' is simply the smallest number.
- heap
- A data structure (priority queue) allowing O(log n) push and pop, and O(1) peek of the extreme element (min/max).
- min-heap
- A heap where the smallest element is always at the root; Python's heapq is a min-heap and heappop returns the minimum.
- top-K
- Finding the K largest (or smallest) elements. This can be done in O(n log K) with a size-K heap, faster than a full sort.
