Where it runs
1. The problem
In the previous lessons you built a heap, and it hands you the smallest element cheaply. Now comes its first real task. You have several lists, and each one is already sorted. For example, logs from k servers, each sorted by time. You need one combined stream, also in time order.
You could glue everything into one array and sort it again. But then the order inside the lists goes to waste, and every line has to sit in memory at the same time. For a few huge streams that is expensive. And the first line of the result cannot go out until all the lines are loaded.
It is better to walk the combined order one element at a time. Each time, hand out the smallest value not yet handed out, and look at as few elements as possible.
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 merge k sorted lists or walk k sorted sequences together. Keep the front item of each list in a min-heap, pop the smallest and push the next item from the same list.
The lesson's mergeK over linked lists, with nodes in the heap instead of positions.
Each row is a sorted list, so seed the heap with every row's first item and pop k times.
Treat the pairs for each nums1[i] as one sorted list, and the same merge gives the first k pairs.
Keep one item per list in the heap and track the current maximum, so the range is that maximum minus the heap's root.