How to use lambdas in python heapq?

Question

In python heapq if you are putting in objects, how can u use a lambda to specify its key? Like heapq.heappush(Q, v, key=lambda x: f(x)).

Thanks

Answer 1

You can't. Or rather, you can't specify it as a lambda. You can however make a heap of tuples, heapq.heappush(Q, (key(v), v)) and heapq.heappop(Q)[1].

Answer 2

Elaborating on my comment, I'd say that U2EF1's solution is valid if f(v) will always return unique values, or if v can be ordered (you could also setup ordering, like in this example).

I made these classes to make it easier to use heapq, and to allow lambdas for sorting.

In general you could do add a unique number to overcome that limitation:

heapq.heappush(Q, create_item(v, f))
(key, v) = heapq.heappop()

# f is your desired function/lambda
# unique_value() generates a different value each time (e.g. a counter)
def create_item(v, f):
    key = (f(v), unique_value())
    return (key, v)

It's a shame there's no way to send a function to heapq... :/