A generic priority queue for Python

python queue
Eli Bendersky picture Eli Bendersky · Jan 2, 2009 · Viewed 93k times · Source

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.

Answer

Charlie Martin picture Charlie Martin · Jan 2, 2009

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.

Related questions

How to check queue length in Python

How to check Queue's length in python? I dont see they provide Queue.lenght in python.... http://docs.python.org/tutorial/datastructures.html from collections import deque queue = deque(["Eric", "John", "Michael"]) how to check the length of this queue? …

Read More
Multiprocessing - Pipe vs Queue

What are the fundamental differences between queues and pipes in Python's multiprocessing package? In what scenarios should one choose one over the other? When is it advantageous to use Pipe()? When is it advantageous to use Queue()?

Read More
Python "FileExists" error when making directory

I have several threads running in parallel from Python on a cluster system. Each python thread outputs to a directory mydir. Each script, before outputting checks if mydir exists and if not creates it: if not os.path.isdir(mydir): …

Read More