推入堆时出现不可排序的类型错误

Question

我有 N 个链表的头部列表，我正尝试使用堆根据它们的值进行合并。

由于 heapq 使用元组中的第一个值在堆中进行排序，因此我编写了以下代码：

 def mergeKLists(self, A): # A contains list of Linked list heads
    nodeList = []
    for i in A:
        nodeList.append((i.val,i)) # Creating a list of tuples : (value, Node address)
    heapq.heapify(nodeList)
    print(nodeList)

这很好用并创建了一个按元组中的第一个值排序的堆。但是，当我试图在此堆上推送更多元素时，它会给我一个无序类型错误：

    t = heapq.heappop(nodeList)
    node  = t[1]
    heapq.heappush(nodeList,(node.next.val,node.next)) # this throws error for node.next parameter

我得到的错误：

heapq.heappush(nodeList,(node.next.val,node))
TypeError: unorderable types: ListNode() < ListNode()

我哪里做错了？

Answer 1

当输入列表有重复值时会出现此错误。在这种情况下，比较具有相同第一个元组成员的两个元组，将导致比较 第二个 元组成员，这是一个未定义的操作。

要避免此错误，请创建 ListNode 个实例 comparable，或者在您的元组中间添加一个唯一的成员：

nodeList.append((i.val, id(i), i))

...并相应地调整其余代码。

推入堆时出现不可排序的类型错误

Unorderable type error while pushing into heap

heap

tuples

python-3.x

heapq