In python there's a built-in heapq
algorithm that gives you push
, pop
, nlargest
, nsmallest
... etc that you can apply to lists. However, there's also the queue.PriorityQueue
class that seems to support more or less the same functionality. What's the difference, and when would you use one over the other?
Queue.PriorityQueue
is a thread-safe class, while the heapq
module makes no thread-safety guarantees. From the Queue
module documentation:
The
Queue
module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads. TheQueue
class in this module implements all the required locking semantics. It depends on the availability of thread support in Python; see thethreading
module.
The heapq
module offers no locking, and operates on standard list
objects, which are not meant to be thread-safe.
In fact, the PriorityQueue
implementation uses heapq
under the hood to do all prioritisation work, with the base Queue
class providing the locking to make this thread-safe. See the source code for details.
This makes the heapq
module faster; there is no locking overhead. In addition, you are free to use the various heapq
functions in different, novel ways, the PriorityQueue
only offers the straight-up queueing functionality.