queueutils
- Priority queues¶
Python comes with a many great data structures, from dict
to collections.deque
, and no shortage of serviceable
algorithm implementations, from sorted()
to bisect
. But
priority queues are curiously relegated to an example documented in
heapq
. Even there, the approach presented is not full-featured
and object-oriented. There is a built-in priority queue,
Queue.PriorityQueue
, but in addition to its austere API, it
carries the double-edged sword of threadsafety, making it fine for
multi-threaded, multi-consumer applications, but high-overhead for
cooperative/single-threaded use cases.
The queueutils
module currently provides two Queue
implementations: HeapPriorityQueue
, based on a heap, and
SortedPriorityQueue
, based on a sorted list. Both use a
unified API based on BasePriortyQueue
to facilitate testing
the slightly different performance characteristics on various
application use cases.
>>> pq = PriorityQueue()
>>> pq.add('low priority task', 0)
>>> pq.add('high priority task', 2)
>>> pq.add('medium priority task 1', 1)
>>> pq.add('medium priority task 2', 1)
>>> len(pq)
4
>>> pq.pop()
'high priority task'
>>> pq.peek()
'medium priority task 1'
>>> len(pq)
3
-
boltons.queueutils.
PriorityQueue
¶
-
class
boltons.queueutils.
BasePriorityQueue
(**kw)[source]¶ The abstract base class for the other PriorityQueues in this module. Override the
_backend_type
class attribute, as well as the_push_entry()
and_pop_entry()
staticmethods for custom subclass behavior. (Don’t forget to usestaticmethod()
).Parameters: priority_key (callable) – A function that takes priority as passed in by add()
and returns an integer representing the effective priority.-
add
(task, priority=None)[source]¶ Add a task to the queue, or change the task’s priority if task is already in the queue. task can be any hashable object, and priority defaults to
0
. Higher values representing higher priority, but this behavior can be controlled by setting priority_key in the constructor.
-
peek
(default=_REMOVED)[source]¶ Read the next value in the queue without removing it. Returns default on an empty queue, or raises
KeyError
if default is not set.
-
-
class
boltons.queueutils.
HeapPriorityQueue
(**kw)[source]¶ A priority queue inherited from
BasePriorityQueue
, backed by a list and based on theheapq.heappop()
andheapq.heappush()
functions in the built-inheapq
module.
-
class
boltons.queueutils.
SortedPriorityQueue
(**kw)[source]¶ A priority queue inherited from
BasePriorityQueue
, based on thebisect.insort()
approach for in-order insertion into a sorted list.