Where it runs
1. The problem
A stream of events goes past: search queries, errors from logs, player scores. You need the 10 biggest values. The rest can be thrown away, and the order inside the top 10 does not matter.
The first idea is to collect everything, sort it and take the first 10. That works while the data fits in memory. But sorting a billion rows to keep 10 of them is wasteful. And a live stream cannot be held in memory at all.
At any moment you need only 10 values. Keep those 10, and let every new value try to take the place of one of them. A small heap does exactly that.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- always need the current smallest/largest
- top k elements
- merge k sorted lists
- running median while items keep arriving
- priority queue / most urgent next
Looks similar, isn't
- Fast sort (merge / quick)
Sorting gives a full order once. A heap gives the front repeatedly, while data still arrives.
- Binary search tree
A search tree orders every pair of nodes. A heap only promises the root.
- Monotonic deque (sliding window max/min)
A deque can drop the element that just expired. A heap has no cheap way to do that.
- Dijkstra's algorithm
Dijkstra is the best-known user of a heap. This page is about the container itself.
n up to 1e6 gives O(log n) per push or pop. Reading the top alone is O(1).
On LeetCode
Problems that ask for the k largest, the k most frequent or the kth largest item. Keep a min-heap capped at k, so its root is the weakest item kept and the cost is O(n log k).
The lesson's capped min-heap kept between calls, with the root as the answer.
Run topK with this k and return the root instead of the whole heap.
Count with a map, then keep the k biggest counts in a capped min-heap.
The same, with a comparator that also breaks equal counts by alphabetical order.