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

Problems
1

https://algo.monster/problems/merge_k_sorted_lists

2

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
3

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.

4

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

5

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

6

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)?

7

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

8

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?

9

Divide and conquer also works well for this problem.

10

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

11

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

12

what is the runtime? nlogk?

13

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

14

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

15

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.

16

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
17

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) {
q.add(i);
}
}

    while (!q.isEmpty()) {
        result.add(q.poll());
    }
    
    return result;
}
18

LC: https://leetcode.com/problems/merge-k-sorted-lists/

19

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.

20

Why not just

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