Heap
K-way merge
Before you start
- Open lesson
Dummy head to merge
Merging two lists picks the smaller head. Merging k lists does the same with a heap choosing among k heads.
Why it matters
Sorted data is often split across log shards, database runs, or timeline feeds that are too large to concatenate and sort again. Copying all values discards the useful order already guaranteed by every source. The merged output must be emitted in order while keeping no more than one available candidate from each input list.
Example
Merge k Sorted Lists
You are given k sorted lists as arrays of values. Merge them into one sorted list and return the values.
- Input
- lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
- Output
- [1, 1, 2, 3, 4, 4, 5, 6]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Merge k Sorted Lists
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]→[1, 1, 2, 3, 4, 4, 5, 6]
The baseline, Collect and sort, is O(N log N) · O(N). The better model below keeps this exact input and removes that bottleneck.
For [[1, 4, 5], [1, 3, 4], [2, 6]], brute force copies and sorts all eight values. The next output is always among heads 1, 1, and 2, so a three-entry heap emits the nodes in order.
For [[1, 4, 5], [1, 3, 4], [2, 6]], heapify the three heads as (1, 0), (1, 1), and (2, 2). Pop list 0's 1, attach it, and push its successor 4. Then pop list 1's 1 and replace it with 3.
Continuing pops 2, 3, 4, 4, 5, and 6, replacing each head only with its own successor. The list index in (value, index, node) breaks the tie between equal 1s and equal 4s, so Python never compares ListNode objects.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.