在python3中使用heapq模块合并k个排序列表 [英] Merging k sorted lists using heapq module in python3

问题描述

问题:- 合并 k 个排序列表.

Problem:- merge k sorted lists.

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

I want to solve this problem using min heap which can be implemented with heapq module in python. Below is the sample code of the function...

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

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

But the problem is that python interpreter is raising an error:

类型错误:'<'ListNode"和ListNode"的实例之间不支持'列表节点'heapq.heappush(listwithoutNone,(node.val, node))

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

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

So, I wanna use the node.val as a minheap node element, since I am passing a tuple, so what change should I do in the code so that minheap will heapify the heap with node.val.

提前致谢.

推荐答案

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

When tuples are compared, their first elements are compared, and then any ties are broken using their second elements, their elements, and so on. For example, (2, "a") < (2, "b") will evaluate to True.

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

Here, you are inserting (node.val, node) tuples into your heap, which attempts to compare them. If there is a tie on the node value, it moves on to the second element of the tuples - the nodes themselves. These are just ListNode instances. Python does not know how to compare two ListNodes, hence the error.

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

To enable comparisons between ListNodes, you need to implement the rich comparison methods. A quick way to do it is to simply implement ListNode.__lt__ and then use the functools.total_ordering decorator:

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

Here we say that comparing two ListNode objects is the same as just comparing their values. With comparisons defined, you don't even need to insert tuples at all. You can just insert ListNode objects directly, and rely on the comparison methods.

这篇关于在python3中使用heapq模块合并k个排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！