Solution: Wrap data with the new comparison

Since the builtin functions don’t directly support cmp functions, we need to build new variants of heapify and heappop:

from heapq import heapify, heappop
from functools import cmp_to_key

def new_heapify(data, cmp):
    s = list(map(cmp_to_key(cmp), data))
    heapify(s)
    return s

def new_heappop(data):
    return heappop(data).obj

Those are used just like your example:

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

Solution: Store Augmented Tuples

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