python - Python2 PriorityQueue 和 Python3 PriorityQueue 的 put 方法有什么区别吗？

Question

我正在解决leetcode的Merge K Sorted Lists problem .

使用 Python2 的 Queue 模块中的 PriorityQueue 的相同算法会为 Python3 的 queue 中的 PriorityQueue 抛出错误> 模块。

Python2版本:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # Load the first node from every linked list into a priority queue
        prQueue = PriorityQueue()
        for node in lists:
            if node:
                prQueue.put((node.val, node))

        head = ListNode(0)
        curr = head
        while not prQueue.empty():
            val, node = prQueue.get()
            curr.next = node
            curr = curr.next
            if node.next:
                prQueue.put((node.next.val, node.next))

        return head.next

上面的代码工作正常。

Python3版本:

from typing import List
from queue import PriorityQueue

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # Load the first node from every linked list into a priority queue
        prQueue = PriorityQueue()
        for node in lists:
            if node:
                prQueue.put((node.val, node))

        head = ListNode(0)
        curr = head
        while not prQueue.empty():
            val, node = prQueue.get()
            curr.next = node
            curr = curr.next
            if node.next:
                prQueue.put((node.next.val, node.next))

        return head.next

上面的代码(Python3版本)不起作用并输出以下错误:

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
    heappush(self.queue, item)
Line 227 in _put (/usr/lib/python3.6/queue.py)
    self._put(item)
Line 143 in put (/usr/lib/python3.6/queue.py)
Line 24 in mergeKLists (Solution.py)
Line 58 in _driver (Solution.py)
Line 71 in &lt;module&gt; (Solution.py)

有什么想法吗？ 谢谢!

Answer 1

问题在于 ListNode 未实现 __lt__ 方法。

这是 python3 中影响您的更改。在 python2 中，这不会成为问题，因为内置的 cmp 函数将用于排序。

当您推送到 PriorityQueue 时，它​​会被排序，为此您需要实现 __lt__ 方法。