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