0

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

我想使用最小堆来解决这个问题，它可以用 python 中的 heapq 模块来实现。下面是函数的示例代码...

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

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

TypeError：'ListNode'和'ListNode'的实例之间不支持'<' heapq.heappush(listwithoutNone,(node.val, node))

所以，我想使用 node.val 作为 minheap 节点元素，因为我正在传递一个元组，所以我应该在代码中做些什么更改，以便 minheap 将使用 node.val 堆化堆。

提前致谢。

4

2 回答 2

1

比较元组时，比较它们的第一个元素，然后使用它们的第二个元素、它们的元素等来打破任何关系。例如，(2, "a") < (2, "b")将评估为True。

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

要启用比较ListNodes，您需要实现丰富的比较方法。一种快速的方法是简单地实现ListNode.__lt__然后使用functools.total_ordering装饰器：

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对象，并依赖比较方法。

于 2021-05-03T10:01:00.437 回答
0

我想你在谈论这个：Leetcode Merge k Sorted Lists

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

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
于 2021-05-03T12:37:50.217 回答