[FIXED] How to heapify by field from custom objects

Issue

I am receiving on server objects from clients ( every object has same structure and have field self.utc_time which contains time of creation of that object). I need to store in some structure so I always have sorted in ascending so when I pop I pop the oldest object by utc_time, not by time when I receive. I thought to use priority queue from heapq but how to say to heaify by utc_time field from custom objects ? Is there better solution ?

Solution

Add the magic __cmp__ comparison method to your class to avoid needing to do the tuple-decoration that Maksim describes:

Python 3

>>> import heapq
>>> class MyObject(object):
...     def __init__(self, val):
...         self.val = val
...     def __lt__(self, other):
...         return self.val < other.val

Python 2

>>> import heapq
>>> class MyObject(object):
...     def __init__(self, val):
...         self.val = val
...     def __cmp__(self, other):
...         return cmp(self.val, other.val)

Code Runner:

>>> 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

Note: Override __lt__ in Python 3, __cmp__ only in Python 2

Answered By - bgporter