如何根据自定义对象的字段进行heapify

Question

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

Answer 1

添加magic __cmp__ comparison method到您的类，以避免需要做的元组装饰是马克西姆描述：

>>> 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 documentation隐式地提供以下解决方案：

堆元件可以是元组。这是旁边的主记录分配比较 值（如任务优先级）有用正在 追踪：

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 question中，建议创建一个易于使用的包装器，该包装器允许使用优先级队列的更简洁的方式。