Hợp nhất k Danh sách được sắp xếp bằng Python

Giả sử chúng ta có một số danh sách, chúng được sắp xếp. Chúng tôi phải hợp nhất các danh sách này thành một danh sách. Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc dữ liệu heap. Vì vậy, nếu danh sách là [1,4,5], [1,3,4], [2,6], thì danh sách cuối cùng sẽ là [1,1,2,3,4,4,5,6] .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo thành một đống

• cho mỗi danh sách liên kết l trong danh sách -

  • nếu không phải là 0, thì hãy chèn I vào một đống

• res:=null và res_next:=null

• Thực hiện một vòng lặp vô hạn -

  • temp:=min of heap

  • nếu heap không có phần tử nào, thì trả về res

  • nếu res bằng 0 thì

    • res:=temp, res_next:=temp

    • temp:=phần tử tiếp theo của temp

    • nếu nhiệt độ không bằng 0, thì hãy chèn nhiệt độ vào heap

    • tiếp theo của res:=null

  • mặt khác -

    • tiếp theo của res_next:=temp, temp:=tiếp theo của tạm thời, res_next:=tiếp theo của res_next

    • nếu tạm thời không null, thì hãy chèn tạm thời vào heap

    • tiếp theo của res_next:=null

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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<self.arr[self.parent(i)].val:
         self.arr[i],self.arr[self.parent(i)] = self.arr[self.parent(i)],self.arr[i]
         i = self.parent(i)
   def heapify(self,i):
      left = self.left(i)
      right = self.right(i)
      smallest = i
      n= len(self.arr)
      if left<n and self.getVal(left)<self.getVal(smallest): smallest = left
      if right <n and self.getVal(right)<self.getVal(smallest): smallest = right
      if smallest!=i:
         self.arr[i],self.arr[smallest] = self.arr[smallest],self.arr[i]
         self.heapify(smallest)
   def extractMin(self):
      n = len(self.arr)
      if n==0:
         return '#'
      if n== 1:
         temp =self.arr[0]
         self.arr.pop()
         return temp
      root = self.arr[0]
      self.arr[0] = self.arr[-1]
      self.arr.pop()
      self.heapify(0)
      return root
class Solution(object):
   def mergeKLists(self, lists):
      heap = Heap()
      for i in lists:
         if i:
            heap.insert(i)
      res = None
      res_next = None
      while True:
         temp = heap.extractMin()
         if temp == "#":
            return res
         if not res:
            res = temp
            res_next = temp
            temp = temp.next
            if temp:
               heap.insert(temp)
            res.next = None
      else:
         res_next.next = temp
         temp = temp.next
         res_next=res_next.next
         if temp:
            heap.insert(temp)
         res_next.next = None
ob = Solution()
lists = [[1,4,5],[1,3,4],[2,6]]
lls = []
for ll in lists:
   l = make_list(ll)
   lls.append(l)
print_list(ob.mergeKLists(lls))

Đầu vào

[[1,4,5],[1,3,4],[2,6]]

Đầu ra

[1, 1, 2, 3, 4, 4, 5, 6, ]