如何在Python 2中向PriorityQueue添加自定义ListNode对象（不可修改ListNode类）

在Python 2环境下，由于无法修改ListNode类添加比较方法，我们可以通过两种常见方式让PriorityQueue根据val属性进行排序：

方法1：使用元组包装ListNode对象 #

Python的元组比较会按元素顺序依次比较，我们可以将val作为元组的第一个元素，后跟ListNode实例。为了避免当多个节点val相同时触发ListNode对象的比较（会报错），可以额外添加一个唯一计数器作为元组的第二个元素。

import Queue

class ListNode: 
    def __init__(self, val=0, next=None): 
        self.val = val 
        self.next = next

# 初始化优先级队列
priority_queue = Queue.PriorityQueue()
count = 0  # 用于处理val相同的情况

# 添加节点到队列
nodes = [ListNode(3), ListNode(1), ListNode(2), ListNode(2)]
for node in nodes:
    priority_queue.put((node.val, count, node))
    count += 1

# 取出并验证排序结果
print("元组包装法输出：")
while not priority_queue.empty():
    _, _, current_node = priority_queue.get()
    print(current_node.val)
# 输出：1, 2, 2, 3

方法2：自定义包装类实现比较逻辑 #

定义一个包装类持有ListNode实例，并实现__lt__方法（Python 2中heapq支持该方法进行比较），将排序逻辑封装在包装类中，完全不修改原ListNode类。

import Queue

class ListNode: 
    def __init__(self, val=0, next=None): 
        self.val = val 
        self.next = next

class NodePriorityWrapper:
    def __init__(self, node):
        self.node = node
    
    def __lt__(self, other):
        # 按val从小到大排序，若需降序则改为`self.node.val > other.node.val`
        return self.node.val < other.node.val

# 初始化队列
priority_queue = Queue.PriorityQueue()

# 添加包装后的节点
priority_queue.put(NodePriorityWrapper(ListNode(3)))
priority_queue.put(NodePriorityWrapper(ListNode(1)))
priority_queue.put(NodePriorityWrapper(ListNode(2)))
priority_queue.put(NodePriorityWrapper(ListNode(2)))

# 取出并验证
print("\n包装类法输出：")
while not priority_queue.empty():
    wrapper = priority_queue.get()
    print(wrapper.node.val)
# 输出：1, 2, 2, 3

两种方法对比 #

• 元组包装法：无需额外定义类，实现简单，但必须维护计数器来避免val相同时的对象比较错误，适合快速实现。
• 包装类法：逻辑更清晰，扩展性强（后续可修改包装类的比较逻辑而不影响原ListNode），无需额外维护计数器，推荐用于复杂场景。

内容的提问来源于stack exchange，提问作者Becay