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 BasePriorityQueue
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
- 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 a real number 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.
- boltons.queueutils.PriorityQueue
alias of
SortedPriorityQueue
- 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.