如何按自定义对象的字段进行堆积

Question

我从客户端接收服务器对象(每个对象具有相同的结构,并具有字段self.utc_time,其中包含创建该对象的时间).我需要存储在一些结构中所以我总是按升序排序所以当我弹出时,我通过utc_time弹出最旧的对象,而不是我收到的时间.我想从heapq中使用优先级队列,但是如何通过自定义对象的utc_time字段来说明heaify？有更好的解决方案吗？

Answer 1

将魔术__cmp__比较方法添加到您的类中以避免需要执行Maksim描述的元组装饰:

>>> import heapq
>>> class MyObject(object):
...     def __init__(self, val):
...         self.val = val
...     def __cmp__(self, other):
...         return cmp(self.val, other.val)
...         
...     
... 
>>> q = []
>>> heapq.heappush(q, MyObject(50))
>>> heapq.heappush(q, MyObject(40))
>>> heapq.heappush(q, MyObject(30))
>>> heapq.heappush(q, MyObject(20))
>>> heapq.heappush(q, MyObject(200))
>>> obj = heapq.heappop(q)
>>> print obj.val
20

注意:__lt__在Python 3中覆盖,__cmp__仅在Python 2中

Answer 2

Python文档隐式提供以下解决方案:

堆元素可以是元组.这对于在跟踪的主记录旁边分配比较值(例如任务优先级)非常有用:

 h = []
 heappush(h, (5, 'write code'))
 heappush(h, (7, 'release product'))
 heappush(h, (1, 'write spec'))
 heappush(h, (3, 'create tests'))
 heappop(h)
   => (1, 'write spec')

您可以以类似的方式执行它 - 存储元组,其中第一个元素将包含utc_time放置到PQ的对象,第二个元素- 对象本身的引用.

在类似的SO问题中,建议创建一个易于使用的包装器,以便更清晰地使用优先级队列.