Welcome to prioq’s documentation!

Note

If object is not listed in documentation it should be considered as implementation detail that can change and should not be relied upon.

class prioq.base.PriorityQueue(*values: Value, key: Optional[Callable[[Value], Key]] = None, reverse: bool = False)[source]

A priority queue is a mutable container that provides constant time lookup of the smallest (by default) element.

Reference: https://en.wikipedia.org/wiki/Priority_queue

__init__(*values: Value, key: Optional[Callable[[Value], Key]] = None, reverse: bool = False) → None[source]

Initializes queue.

Complexity: O(log len(values)).

Parameters
  • values – initial values

  • key – function of one argument to calculate priority.

  • reverse – flag, if set to True specifies that values should be processed in descending order (from highest priority to lowest).

>>> from prioq.base import PriorityQueue
>>> values = range(-5, 5)
>>> queue = PriorityQueue(*values, key=abs, reverse=True)
>>> len(queue) == len(values)
True
>>> queue.key is abs
True
>>> queue.reverse
True
__eq__(other: prioq.base.PriorityQueue[Value]) → bool[source]

Checks if the queue is equal to the given one.

Complexity: O(len(self) * log len(self) + len(other) * log len(other)).

>>> queue = PriorityQueue(*range(10))
>>> queue == PriorityQueue(*range(10))
True
>>> queue == PriorityQueue(*range(10), reverse=True)
False
>>> queue == PriorityQueue(*range(20))
False
>>> queue == PriorityQueue(*range(5))
False
__len__() → int[source]

Returns number of elements in the queue.

Complexity: O(1).

>>> queue = PriorityQueue(*range(5))
>>> len(queue)
5
clear() → None[source]

Removes all values from the queue.

Complexity: O(1).

>>> queue = PriorityQueue(*range(5))
>>> queue.clear()
>>> queue
PriorityQueue(key=None, reverse=False)
peek() → Value[source]

Returns front value of the queue.

Complexity: O(1).

>>> queue = PriorityQueue(*range(5))
>>> queue.peek()
0
>>> queue.push(-1)
>>> queue.peek()
-1
>>> queue.push(0)
>>> queue.peek()
-1
pop() → Value[source]

Pops front value from the queue.

Complexity: O(1).

>>> queue = PriorityQueue(*range(5))
>>> queue.pop()
0
>>> queue
PriorityQueue(1, 2, 3, 4, key=None, reverse=False)
>>> queue.pop()
1
>>> queue
PriorityQueue(2, 3, 4, key=None, reverse=False)
push(value: Value) → None[source]

Adds value to the queue.

Complexity: O(log len(self)).

>>> queue = PriorityQueue(*range(5))
>>> queue.push(-1)
>>> queue
PriorityQueue(-1, 0, 1, 2, 3, 4, key=None, reverse=False)
>>> queue.push(10)
>>> queue
PriorityQueue(-1, 0, 1, 2, 3, 4, 10, key=None, reverse=False)
remove(value: Value) → None[source]

Removes value from the queue and if absent raises ValueError.

Complexity: O(len(self)).

>>> queue = PriorityQueue(*range(5))
>>> queue.remove(0)
>>> queue
PriorityQueue(1, 2, 3, 4, key=None, reverse=False)
>>> queue.remove(4)
>>> queue
PriorityQueue(1, 2, 3, key=None, reverse=False)
values() → List[Value][source]

Returns elements of the queue.

Complexity: O(len(self) * log len(self)).

>>> queue = PriorityQueue(*range(5))
>>> queue.values()
[0, 1, 2, 3, 4]