In Python, heapq.heapify doesn't take cmp or key functions as arguments like sorted does

Question

I'm using python2.6. Is it available in higher version of python?
Else is there any other way I can maintain priority queues for list of objects of non-trivial classes? What I need is something like this

>>> l = [ ['a', 3], ['b', 1] ] >>> def foo(x, y): ...   return x[1]-y[1] >>> heap = heapify(l, cmp=foo) 

Any suggestions ?

Answer 1

The traditional solution is to store (priority, task) tuples on the heap:

pq = [ ] heappush(pq, (10, task1)) heappush(pq, (5, task2)) heappush(pq, (15, task3)) priority, task = heappop(pq) 

This works fine as long as no two tasks have the same priority; otherwise, the tasks themselves are compared (which might not work at all in Python 3).

The regular docs give guidance on how to implement priority queues using heapq:

http://docs.python.org/library/heapq.html#priority-queue-implementation-notes

Answer 2

Just write an appropriate __lt__ method for the objects in the list so they sort correctly:

class FirstList(list):     def __lt__(self, other):         return self[0] < other[0]  lst = [ ['a', 3], ['b', 1] ]  lst = [FirstList(item) for item in lst] 

Only __lt__ is needed by Python for sorting, though it's a good idea to define all of the comparisons or use functools.total_ordering.

You can see that it is working by using two items with the same first value and different second values. The two objects will swap places when you heapify no matter what the second values are because lst[0] < lst[1] will always be False. If you need the heapify to be stable, you need a more complex comparison.