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

• 한 번의 무한 루프 수행 -

  • temp :=최소 힙

  • 힙에 요소가 없으면 res

    를 반환합니다.

  • res가 0이면

    • res :=임시, res_next :=임시

    • temp :=temp의 다음 요소

    • temp가 0이 아니면 temp를 힙에 삽입

    • 다음 res :=null

  • 그렇지 않으면 -

    • res_next의 다음 :=temp, temp :=temp의 다음, res_next :=res_next의 다음

    • temp가 null이 아니면 temp를 힙에 삽입

    • res_next의 다음:=null

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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, ]