How do you merge k sorted lists efficiently?
You put the front of every list into a heap, and then you take the smallest one out and put the next one from that same list into the heap.
import heapq
def merge_sorted(lists):
heap = []
positions = [0] * len(lists)
for index, values in enumerate(lists):
if values:
heap.append((values[0], index))
heapq.heapify(heap)
result = []
while heap:
value, index = heapq.heappop(heap)
result.append(value)
positions[index] += 1
if positions[index] < len(lists[index]):
next_value = lists[index][positions[index]]
heapq.heappush(heap, (next_value, index))
return result
So how does it work? The heap holds one value from each list, and it always holds the smallest value that is still waiting. So the value you take out is the smallest of all the values that are left, and the answer comes out in order.
And when you take a value out of a list you put the next value from that same list into the heap. So the heap always has the front of every list that still has something in it.
the lists [1, 4, 7], [2, 5, 8], [3, 6, 9]
the heap (1, 0), (2, 1), (3, 2)
take 1, the heap is now (2, 1), (3, 2), (4, 0)
take 2, the heap is now (3, 2), (4, 0), (5, 1)
And the pair in the heap is the value and the index of the list it came from. The index is there so that the heap can tell two values apart, because Python compares tuples item by item and it cannot compare two lists. If two values are the same then the smaller list index wins, which gives a fixed and fair order.
And the complexity is O of N log k for the time, where N is the total number of values across all the lists and k is the number of lists. Every value goes into the heap once and comes out once. And the space is O of k for the heap and O of N for the answer.
And there is a simpler version that is worth knowing about. You merge the lists two at a time, using the merge from the earlier topic. Merging k lists two at a time is O of N log k as well, and the code is shorter if you already have a two list merge.
So the rule to remember is this. The heap holds one value from each list, and that is enough to keep the answer in order.
The last question in this topic shows the library helper.