Python – A generic priority queue for Python


I need to use a priority queue in my Python code, and:

  • am looking for any fast implementations for priority queues
  • optimally, I'd like the queue to be generic (i.e. work well for any object with a specified comparison operator).

Looking around for something efficient, I came upon heapq, but:

  • I'm looking for something faster than heapq, which is implemented in native Python, so it's not fast.
  • It looks good, but seems to be specified only for integers. I suppose it works with any objects that have comparison operators, but it doesn't specify what comparison operators it needs.
  • Update: Re comparison in heapq, I can either use a (priority, object) as Charlie Martin suggests, or just implement __cmp__ for my object.

Best Solution

You can use Queue.PriorityQueue.

Recall that Python isn't strongly typed, so you can save anything you like: just make a tuple of (priority, thing) and you're set.