如何根據自定義對象的字段進行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中，建議創建一個易於使用的包裝器，該包裝器允許使用優先級隊列的更簡潔的方式。