Heap · Stage 2 of 3
Top-K Elements
Keep a heap of size k, and evict its top whenever it overflows
Foundations
In the first lesson, the heap held every item and handed out the smallest. Now, what if you only need the k largest of many items, or of a stream that never ends, and cannot keep them all?
Keep a min-heap of at most k items. Push each new item; if the heap grows to k + 1, pop the top. The top is the smallest item kept, the weakest of the current best k, so anything smaller than it can never make the cut. Each item costs O(log k), and memory stays O(k) however many items pass through.
Find the 3 largest values of nums = [7, 1, 5, 3, 6]. After 7, 1, and 5 the heap is full, with 1 on top. Pushing 3 makes four items, so the top, 1, is popped; pushing 6 pops 3. The heap ends as [5, 6, 7], the three largest, and its top, 5, is the third largest.
nums
heap, k = 3
Case Scenario
The problem
K Closest Points to Origin
Return the k points closest to (0,0) by Euclidean distance. Break distance ties by smaller x, then smaller y. Return the selected points sorted by x, then y.
- Input
- points = [[3, 3], [5, -1], [-2, 4]], k = 2
- Output
- [[-2, 4], [3, 3]]
K Closest Points to Origin keeps the k points nearest to (0, 0), measured by squared distance x * x + y * y. Nearest means smallest, so the bounded heap must evict the farthest: store negated distances, and the top is the farthest point kept. For points = [[3, 3], [5, -1], [-2, 4]] and k = 2, the answer is [[-2, 4], [3, 3]].
The direct approach sorts every point by distance and takes the first k. It is simple, but it costs O(n log n) however small k is, and it needs every point in memory at once, which a stream of millions of points does not allow.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.