How to heapify by field from custom objects

Question

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 ?

Answer 1

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

Answer 2

Python documentation implicitly provides the following solution:

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:

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

You can do it in a similar fashion - store tuples where the first element will contain a utc_time of an object being placed to the PQ and the second - a reference to object itself.

In a similar SO question it's proposed to create an easy-to-use wrapper that would allow a cleaner way of working with a priority queue.