在python3中使用heapq模块合并k个排序列表

Question

问题：-合并k个排序列表

我想用min-heap解决这个问题，它可以用python中的heapq模块实现。 下面是函数的示例代码

heapq.heappush(listwithoutNone,(node.val, node))
        

但问题是python解释器引发了一个错误：

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' heapq.heappush(listwithoutNone,(node.val, node))

因此，我想使用node.val作为minheap节点元素，因为我要传递一个元组，所以我应该在代码中做什么更改，以便minheap将堆与node.val进行heapify

提前谢谢

Answer 1

当比较元组时，会比较元组的第一个元素，然后使用元组的第二个元素、第二个元素等打破任何联系。例如，(2, "a") < (2, "b")将计算为True

这里，您正在将(node.val, node)元组插入堆中，堆将尝试比较它们。如果节点值上有一个tie，那么它将移动到元组的第二个元素——节点本身。这些只是ListNode实例。Python不知道如何比较两个ListNodes，因此出现了错误

要启用ListNodes之间的比较，需要实现rich comparison methods。 一种快速的方法是简单地实现ListNode.__lt__，然后使用^{}装饰器：

import heapq
from functools import total_ordering


@total_ordering
class ListNode:
    def __init__(self, value: float, label: str) -> None:
        self.value = value
        self.label = label

    def __lt__(self, other: 'ListNode'):
        return self.value <= other.value

    def __str__(self):
        return f"ListNode(label={self.label}, value={self.value})"



nodes = []
a =  ListNode(5, "A")
b = ListNode(3, "B")
c = ListNode(5, "C")
heapq.heappush(nodes, a)
heapq.heappush(nodes, b)
heapq.heappush(nodes, c)

while nodes:
    x = heapq.heappop(nodes)
    print(x)

这里我们说比较两个ListNode对象与比较它们的值是一样的。定义了比较之后，您甚至不需要插入元组。您可以直接插入ListNode对象，并依赖于比较方法

Answer 2

我想你说的是：Leetcode合并k个排序列表

我正在为您分享一个可行的解决方案：

head = curr = ListNode(0)    # Creating a dummy node
    lst = []
    for l in lists:
        if l:
 # Here we need to first push val so that heap can know which is minimum and which is maximum. 
 # If we insert directly node then heap can't work proper way (in this case heapq.heappop doesn't return minimum node).    
            lst.append((l.val,l))    

    
    heapq.heapify(lst)
    while lst:
        val,node = heapq.heappop(lst)
        curr.next = node
        curr = curr.next
        node = node.next
        if node:
            heapq.heappush(lst,(node.val,node))
    return head.next