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 ?

question from:https://stackoverflow.com/questions/7803121/in-python-heapq-heapify-doesnt-take-cmp-or-key-functions-as-arguments-like-sor

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