Merge many sorted lists
Combine k sorted lists into one sorted list by keeping the front value of each list in a min-heap and always taking the smallest. About 16 minutes.
One candidate per list
You have k lists, each sorted. The overall smallest unused value must be at the front of one of them. So keep the front value of every list in a min-heap. The top of the heap is the next value of the merged output.
A heap entry must remember where it came from: the value, which list it belongs to, and its position in that list.
heap = [] heapq.heappush(heap, (lst[0], i, 0)) # value, which list, position
The fronts are 2, 1 and 4. Take 1 from the second list. It now shows 3.
Replace what you took
Take the smallest entry off the heap and add its value to the output. Its list now has a new front, the value at the next position, if there is one. Push that into the heap.
Repeat until the heap is empty. Empty lists never enter the heap. The output has all the values in order, and the heap never holds more than k entries.
nxt = lists[i][pos + 1] # the next from the same list
After taking a value from a list, what goes into the heap?
- AThe next value from the same list, if there is one
- BAll the remaining values of that list
- CNothing
Show the answer
The next value from the same list, if there is one. That list's front has changed, so its new front becomes a candidate.
Merge k sorted lists
You are given an array lists of k arrays, each sorted in non-decreasing order. Merge all of them into a single sorted array and return it. Some of the arrays may be empty.
lists = [[1, 4, 5], [1, 3, 4], [2, 6]] → [1, 1, 2, 3, 4, 4, 5, 6]
0 ≤ k ≤ 1,000 · 0 ≤ total number of values ≤ 3,000 · -10,000 ≤ value ≤ 10,000