Priority Queue¶

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

• n is the number of elements currently in the priority queue.

☕️ API¶

Here are all of the public methods that can be used with PriorityQueue() objects:

class extra.lists.priority_queue.PriorityQueue(max_capacity=inf, seed=None)¶

A priority queue is a collection of prioritized elements that allows arbitrary element insertion, and allows the removal of the element that has the highest priority. When an element is added to a priority queue, the user designates its priority by providing an associated priority. The element with the minimum priority will be the next to be removed from the queue.

__init__(max_capacity=inf, seed=None)¶

Creates a PriorityQueue() object!!

Parameters:	max_capacity (int) – It’s a positive integer representing the maximum number of elements a PriorityQueue() should contain. (default: inf) seed (int, optional) –
Raises:	TypeError: – If the type of max_capacity isn’t int or float. ValueError: – If the given value of max_capacity is less than zero.

Example

>>> pq = PriorityQueue()
>>> type(pq)
<class 'extra.lists.priority_queue.PriorityQueue'>
>>> pq._max_capacity
inf

You can define the maximum capacity for your own instance:

>>> pq = PriorityQueue(10)
>>> pq._max_capacity
10

Note

If you passed a float number as the maximum capacity, then the value that get assigned is the rounding of that number:

>>> pq = PriorityQueue(10.6)
>>> pq._max_capacity
11

__len__()¶

Gets the length of the PriorityQueue() instance in constant time.

Returns:	The length of the PriorityQueue() instance. By Length, I mean the number of elements of in the instance.
Return type:	int

Examples

>>> pq = PriorityQueue()
>>> len(pq)
0
>>> pq.enqueue(1)
>>> pq.enqueue(2)
>>> pq.enqueue(3)
>>> len(pq)
3

__repr__()¶

Represents the PriorityQueue() instance as a string.

Returns:	The string-representation of the PriorityQueue() instance.
Return type:	str

Example

>>> pq = PriorityQueue()
>>> pq.enqueue(10, priority=1)
>>> pq.enqueue(20, priority=5)
>>> pq
─┬────┬────┬─
⟶│ 20 │ 10 │⟶
─┴────┴────┴─

You can show the priority of these items by enabling SHOW_PRIOIRTY static variable:

>>> PriorityQueue.SHOW_PRIORITY = True
>>> pq
─┬────────┬────────┬─
⟶│ 20|P:5 │ 10|P:1 │⟶
─┴────────┴────────┴─

clear()¶

Removes all objects within the PriorityQueue() instance in constant time.

Example

>>> pq = PriorityQueue()
>>> pq.enqueue(1)
>>> pq.enqueue(2)
>>> pq.enqueue(3)
>>> pq
─┬───┬───┬───┬─
⟶│ 3 │ 2 │ 1 │⟶
─┴───┴───┴───┴─
>>> len(pq)
3
>>> pq.clear()
>>> pq
─┬
⟶│
─┴
>>> len(pq)
0

Note

When you clear the PriorityQueue() instance, the max_capacity of the cleared instance remains the same as the one before.

dequeue(lowest_priority=False)¶

Pops the item that has the highest priority from the PriorityQueue() instance in constant time.

Returns:	The item that has the highest priority in the PriorityQueue().
Return type:	object
Raises:	UserWarning: – If the PriorityQueue() instance is empty!!

Example

>>> pq = PriorityQueue()
>>> pq.dequeue()
UserWarning: Dequeuing from empty `extra.PriorityQueue()`!!
>>> pq.enqueue(10, priority=0)
>>> pq.enqueue(20, priority=2)
>>> PriorityQueue.SHOW_PRIORITY = True
>>> pq
─┬────────┬────────┬─
⟶│ 20|P:2 │ 10|P:0 │⟶
─┴────────┴────────┴─
>>> pq.dequeue()
20
>>> pq
─┬────────┬─
⟶│ 10|P:0 │⟶
─┴────────┴─

enqueue(item, priority=None)¶

Inserts the given item to the end of the PriorityQueue(), it does that in constant time.

Parameters:	item (object) – The python object to be pushed to the PriorityQueue(). priority (int or float) – The priority is a numeric value that indicates how important this object is. The bigger this numeric value is, the higher its priority in the queue is. If priority=None, then a random integer number will be assigned.
Raises:	UserWarning: – If the PriorityQueue() instance was full!! By “full”, I mean the number of items in the PriorityQueue() equals to the assigned maximum capacity. ValueError: – If the given item is None. TypeError: – It can be raised due to one of the following reasons: If the given item is an instance of Extra. If the given priority isn’t a number.

Example

>>> pq = PriorityQueue(max_capacity=2)
>>> pq
─┬
⟶│
─┴
>>> pq.enqueue(1)
>>> pq.enqueue(2)
>>> pq
─┬───┬───┬─
⟶│ 2 │ 1 │⟶
─┴───┴───┴─
>>> pq.enqueue(3)
UserWarning: Enqueuing to a full `extra.PriorityQueue()` could lead             to missing values!!
>>> pq
─┬───┬───┬─
⟶│ 3 │ 2 │⟶
─┴───┴───┴─

is_empty()¶

Checks if PriorityQueue() instance is empty or not in constant time.

Returns:	A boolean flag showing if the PriorityQueue() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> pq = PriorityQueue()
>>> pq.is_empty()
True
>>> pq.enqueue(5)
>>> pq.is_empty()
False

is_full()¶

Checks if PriorityQueue() instance is at full-capacity in constant time.

Returns:	A boolean flag showing if the PriorityQueue() instance is full or not. True shows that this instance is full and False shows it’s not full.
Return type:	bool

Example

>>> pq = PriorityQueue(max_capacity=2)
>>> pq.is_full()
False
>>> pq.enqueue(5)
>>> pq.is_full()
False
>>> pq.enqueue(10)
>>> pq.is_full()
True

top()¶

Returns the first item inserted to the PriorityQueue() instance in constant time.

Returns:	The PriorityQueue() instance’s first inserted item.
Return type:	object
Raises:	IndexError: – If the PriorityQueue() instance is empty!!

Example

>>> pq = PriorityQueue()
>>> pq.top()
IndexError: Can't retrieve from an empty `extra.PriorityQueue()`!!
>>> pq.enqueue(10)
>>> pq.enqueue(20)
>>> pq
─┬────┬────┬─
⟶│ 20 │ 10 │⟶
─┴────┴────┴─
>>> pq.top()
10