在Python中合并k个排序列表

假设我们有一些列表,这些列表已排序。我们必须将这些列表合并为一个列表。为了解决这个问题,我们将使用堆数据结构。因此,如果列表为[1,4,5],[1,3,4],[2,6],则最终列表将为[1,1,2,3,4,4,5,6] 。

为了解决这个问题,我们将遵循以下步骤-

  • 堆一堆

  • 对于列表中的每个链接列表l-

    • 如果不为0,则将I插入堆

  • res:= null和res_next:= null

  • 做一个无限循环-

    • 下一个res_next:= temp,temp:=下一个temp,res_next:=下一个res_next

    • 如果temp不为null,则将temp插入堆中

    • 下一个res_next:= null

    • res:= temp,res_next:= temp

    • temp:= temp的下一个元素

    • 如果temp不为零,则将temp插入堆中

    • 下一个res:= null

    • temp:=最小堆

    • 如果堆没有元素,则返回res

    • 如果res为0,则

    • 否则-

    示例

    让我们看下面的实现以更好地理解-

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

    输入项

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

    输出结果

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