# Merge K Sorted Lists - Priority Queue / Heap / Top K

another way to do it instead of keeping head_index is to pop(0) on the list:

def merge_k_sorted_lists(lists: List[List[int]]) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE
minHeap = []
for i, l in enumerate(lists):
heapq.heappush(minHeap,(l.pop(0),i))
res = []
while minHeap:
smallest , i = heapq.heappop(minHeap)
res.append(smallest)
if lists[i]:
el =lists[i].pop(0)
heapq.heappush(minHeap,(el,i))

``````return res
``````

def merge_k_sorted_lists(lists: List[List[int]]) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE

``````heap = []

for arr in lists:
for item in arr:
heapq.heappush(heap, item)

result = []

while heap:
result.append(heapq.heappop(heap))

return result
``````

Anything wrong in this approach…?
It’s quite simple and straight forward.
Just utilizing the heap property.

The space complexity is higher. Heap would have all the elements vs K elements in the given solution.

That makes the algorithm O(n^2), popping from the front causes the whole list to be shifted back, unless you use a deque.

from typing import List
import heapq
def merge_k_sorted_lists(lists: List[List[int]]) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE
res = []
heap = []
for li in lists:
heap.extend(li)
heapq.heapify(heap)
for i in range(len(heap)):
res.append(heapq.heappop(heap))
return res

Would this be O(nlogn)?

You don’t need to store all the sublists in the heap.
for current_list in lists:
# push first number of each list into the heap
heappush(heap, (current_list[0], current_list, 0)) # 1

Instead, just store the index of the current_list.
Big difference in practical space complexity

could I not just put all elements of all lists into one minheap and pop from there? Would that not be the same time complexity as the provided solution?

Divide and conquer also works well for this problem.

In that case, the heap would have size = total number of element in all lists, whereas in the provided solution heap size = number of lists

It’s the references, not the actual object that’s being stored tho

what is the runtime? nlogk?

I believe this solution to be simpler to understand while doing exactly the same:

def merge_k_sorted_lists(lists: List[List[int]]) → List[int]:
heap = []
result = []
for i in range(len(lists)):
heappush(heap, (lists[i].pop(0), i))
while heap:
elem, l = heappop(heap)
if lists[l]:
heappush(heap, (lists[l].pop(0), l))
result.append(elem)
return result

agree. I did the same thing. Unless there is some constraint on the problem that algomonster didn’t tell us (has happened before).

I think it is worth showing the most basic answer (pushing all elements into the heap and then poping them one by one) as a “brute-force” before optimizing for space complexity and using the heap with size K.

Here is my first attempt. I believe the official solution is more efficient as they don’t have the extra complexity of slicing a new array present in my solution.

from typing import List

import heapq

def merge_k_sorted_lists(lists: List[List[int]]) → List[int]:

``````heapq.heapify(lists)

output = []
while len(lists) > 0:
nums = heapq.heappop(lists)
output.append(nums[0])
remainder = nums[1:]
if len(remainder) > 0:
heapq.heappush(lists, remainder)
return output
``````

My solution:

public static List mergeKSortedLists(List<List> lists) {
List result = new ArrayList<>();
PriorityQueue q = new PriorityQueue<>();
for (List list : lists) {
for (Integer i : list) {
}
}

``````    while (!q.isEmpty()) {
}

return result;
}
``````

There is no `&` in `std::vector<int> current_list;` . So, it is not a reference but copy of data.
Just adding a `&` to `std::vector<int> & current_list;` would make it very efficient.

Why not just

``````    l1 = [j for i in lists for j in i]
heapify(l1)
return [heappop(l1) for _ in range(len(l1))]
``````