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)

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 use staticmethod()).

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)

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)

Read the next value in the queue without removing it. Returns default on an empty queue, or raises KeyError if default is not set.

pop(default=_REMOVED)

Remove and return the next value in the queue. Returns default on an empty queue, or raises KeyError if default is not set.

remove(task)

Remove a task from the priority queue. Raises KeyError if the task is absent.

class boltons.queueutils.HeapPriorityQueue(**kw)

A priority queue inherited from BasePriorityQueue, backed by a list and based on the heapq.heappop() and heapq.heappush() functions in the built-in heapq module.

boltons.queueutils.PriorityQueue

alias of SortedPriorityQueue

class boltons.queueutils.SortedPriorityQueue(**kw)

A priority queue inherited from BasePriorityQueue, based on the bisect.insort() approach for in-order insertion into a sorted list.