在 python 中使用 heapq 作为优先级列表的问题

Question

我无法理解为什么我的以下代码会引发错误。

我正在尝试基于 Python 的 heapq 模块构建优先级列表。与模块的基本示例的唯一区别是想要将它与其中的自定义对象一起使用，而不是简单的 (int,int) 或 (int,str) 元组。

import heapq

class MyObject():

 def __init__(self,a=0,name='toto'):

     self.a = a
     self.name = name

if __name__ == '__main__':

 priority_list = []
 heapq.heappush(priority_list,(1,MyObject()))
 heapq.heappush(priority_list,(1,MyObject()))

这是我的错误：

heapq.heappush(priority_list,(1,MyObject()))

TypeError: '<' not supported between instances of 'MyObject' and 'MyObject'

如果我使用不同的密钥插入堆中，则不会引发错误，但 heapq 不应该处理相同的密钥吗？我不太理解这种行为。

非常感谢

Answer 1

堆有属性最小的对象总是在最上面。为了 Python 保持不变，它必须有某种方法来确定哪个对象更小。你的 MyObject class 没有提供这个。

您可以定义 __gt__ 或 __lt__ 来启用它。

Answer 2

未为您的 class 定义运算符 <。这样 heapq 无法定义优先级。

ob1 = MyObject()
ob1 < ob1

加注

TypeError: unorderable types: MyObject() < MyObject()

然后您必须定义逻辑运算符。有关详细信息，请参阅 this。

class MyObject():
    def __init__(self,a=0,name='toto'):
        self.a = a
        self.name = name

    def __lt__(ob1, ob2):
        return ob1.a < ob2.a

ob1 = MyObject()
ob1 < ob1 # returns False

在 python 中使用 heapq 作为优先级列表的问题

Issue using heapq in python for a priority list

python

heap

list

object

priority-queue