পাইথনে Merge k Sorted Lists

ধরুন কিছু সর্টেড লিস্ট আছে। আমাদের এই লিস্টগুলোকে একত্রিত করে একটি লিস্ট বানাতে হবে। সমাধানে হিপ ডেটা স্ট্রাকচার ব্যবহার করা হবে। যেমন লিস্টগুলো [1,4,5], [1,3,4], [2,6] হলে ফাইনাল লিস্ট হবে [1,1,2,3,4,4,5,6]。

সমাধানের ধাপগুলো −

একটি হিপ তৈরি করুন
প্রতিটি লিঙ্কড লিস্ট l-এর জন্য − যদি l নন-নাল থাকে তবে হিপে ইনসার্ট করুন
res := null, res_next := null
একটি ইনফাইনাইট লুপ − temp = heap.extractMin(); যদি হিপ খালি থাকে তবে res রিটার্ন করুন; যদি res নাল থাকে তবে res = temp, res_next = temp, temp = temp.next, যদি temp থাকে তবে হিপে ইনসার্ট করুন, res.next = None; অন্যথায় res_next.next = temp, temp = temp.next, res_next = res_next.next, যদি temp থাকে তবে হিপে ইনসার্ট করুন, res_next.next = None

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

class ListNode:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next
def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head
def print_list(head):
    ptr = head
    print('[', end = "")
    while ptr:
        print(ptr.val, end = ", ")
        ptr = ptr.next
    print(']')
class Heap:
    def __init__(self):
        self.arr = []
    def print_heap(self):
        res = " "
        for i in self.arr:
            res += str(i.val) + " "
        print(res)
    def getVal(self,i):
        return self.arr[i].val
    def parent(self,i):
        return (i-1)//2
    def left(self,i):
        return (2*i + 1)
    def right(self,i):
        return (2*i + 2)
    def insert(self,value):
        self.arr.append(value)
        n = len(self.arr)-1
        i = n
        while i != 0 and self.arr[i].val
ইনপুট
[[1,4,5],[1,3,4],[2,6]]
আউটপুট
[1, 1, 2, 3, 4, 4, 5, 6, ]