Updated July 28, 2023
Introduction to Priority Queues in Python
A queue, in general, can be defined as an arrangement or storage order of data/ elements using the principle ‘First In First Out’ (FIFO). In python, priority queueing is an extension of the FIFO method, where the data/elements are arranged in a prioritized order. A Priority Queue should obey a few behavioral constraints, such as every data/ element in the system should have a priority assigned to it, data/ element with higher priority are placed before a data/ element with lower priority, and if more than one data/ element is holding same priority then FIFO is followed for its placement. In python, this is achieved using the heap sort or list function.
Examples to Implement Priority Queues
Here are some of the examples of priority queues in python, which are as follows:
Example #1
This is an example of priority queues using a python sorted list.
Code:
#Implementing Priority Queues with Sorted list
#declaring empty list
que=[]
#adding elements to the list
que.append((5,'Medium priority task'))
que.append((1,'High priority task'))
que.append((10,'Low priority task'))
#list is sorted evertime a new element is inserted
que.sort(reverse=True)
print("Tasks with their priorities :")
#looping through sorted list
while que:
queue_item=que.pop()
print(queue_item)Output:
Explanation: First, we have declared an empty list into which elements are inserted using the append() method of the List class. The list is then sorted in ascending order. While the loop is used to retrieve elements from the list using the pop() method. This is a manual method of implementing priority queues.
Pros and Cons of this Approach: It is best suitable to identify and delete the smallest or largest element quickly. The main drawback is that inserting a new element into the list is a slow operation. Therefore, sorted lists are suitable only when there are few insertions.
Example #2
This is an example of priority queues using the heapq module. A binary heap is often used to implement priority queues. This Python provides a heapq library. But heapq only provides a min-heap implementation.
Min heap: A complete binary tree where the key at the root must be minimum among all the keys present in the Binary heap.
Code:
# Implementing Priority queue using heapq module
# Importing heapq module
import heapq
# declaring empty list
que = []
# adding elements to the list
heapq.heappush(que, (5, 'Medium Priority task'))
heapq.heappush(que, (1, 'High priority task'))
heapq.heappush(que, (10, 'low priority task'))
# dequeuing elements
print("Elements will be dequeued according to their prorities")
while que:
deque_item = heapq.heappop(que)
print(deque_item)Output:
Explanation: First, we’ve imported the heapq module then created an empty list. Using the heappush() method of the heapq module, we have inserted the elements into the list. While loop is then used to pop elements out of the list. It can be clearly depicted in the output that the order in which the elements are entered (5 -> 1 -> 10) is different from the dequeuing order (1 -> 5 -> 10).
Example #3
This is an example of priority queues using the queue.PriorityQueue class. Python provides a built-in implementation of the priority queue data structure. Python uses a binary heap to implement priority queues.
Min heap: A complete binary tree where the key at the root must be minimum among all the keys present in the Binary heap.
Max heap: A complete binary tree where the key at the root must be maximum among all the keys present in the Binary heap.
1. This is the basic example to implement a priority queue using a queue. PriorityQueue class.
Code:
# Implementing priority queue using queue.PriorityQueue class
import queue as PQ
q = PQ.PriorityQueue()
q.put(10)
q.put(1)
q.put(5)
print("Dequeing elements")
while not q.empty():
print (q.get())Output:
Explanation: The queue module is imported. An object “q” of PriorityQueue() is then created. Elements are inserted into this queue using the put() method. After that, a while loop is used to retrieve or dequeue the elements using the get() method. Queue stores the elements according to their priorities ( 1 -> 5 -> 10 ) not by the order of element creation/insertion(10 -> 1 -> 5) as shown in the above output.
2. Below is the example of a priority queue that can store any object in addition to a basic built-in primitive.
Code:
# Implementing priority queue using Queue.PriorityQueue class
import queue as PQ
q = PQ.PriorityQueue()
q.put((10,'Low priority task'))
q.put((1,'High priority task'))
q.put((5,'Medium priority task'))
print("Dequeing elements")
while not q.empty():
print (q.get())Output:
Here, we have inserted a tuple-> task name along with its priority.
Time Complexity using the queue.PriorityQueue Class
| Operation | Worst-case Time Complexity |
| Insertion | O(logn) |
| Deletion | O(logn) |
Why are Priority Queues Used?
Priority Queues have many applications. Some all listed below:
- Graph algorithms: The priority queues are used in Graph algorithms like Dijkstra’s Shortest path and Prim’s Minimum spanning trees.
- Data Compression: It is used in Huffman codes which are used to compress data.
- Artificial Intelligence: A* search algorithm finds the shortest path between two vertices of a weighted graph, trying out the most promising routes first. The priority queue is used to keep track of unexplored routes; the one which has a lower bound on the total length is smallest is given the highest priority.
- Operating System: It is also used in the OS for load balancing and Interrupt handling. Priority queues are also used in Process Scheduling, where a high priority task is assigned to the CPU before a low priority task.
Conclusion
A priority queue is a modified version of basic queues where the priority of tasks is considered rather than their insertion order. There are multiple ways to implement priority queues in python, as explained above. Each has slightly different use cases. But PriorityQueue is a good default choice because it has a nice object-oriented interface.
Recommended Articles
This is a guide to Priority Queues in Python. Here we discuss the basic concept, examples of priority queues in python and its detailed explanation, and the uses of priority queues. You may also look at the following articles to learn more –
