Are you tired of hearing some strange concepts of data structures like priority queue? No more confusions because here you’ll get to know everything about the priority queue. And we will be using Python language to write some code so let’s say more specifically Python priority queue. We will use Python 3. Many people who have just begun to explore these Data structure terms like a queue, stack, heap and priority queue are usually confused between heap and priority queue. So we will talk about their differences and similarities.
The priority queue in Python or any other language is a particular type of queue in which each element is associated with a priority and is served according to its preference. If elements with the same priority occur, they are performed according to their order in the queue. Generally, the value of the element itself is considered for assigning the priority.
What is a Priority Queue In-depth
Simply, a priority queue is an ADT similar to queue in Data structure (a very important subject of CS major). But what makes it different from queue is the elements in Priority queue has some kind of priority over other elements.
What does priority of those elements mean to us? Do they really worth my time? Yes. It is important for you to know why they exist if you are willing to learn and master Priority queue and other aspects of it like Python priority queue comparator or priority queue max size in python, etc. They simply exist because priority decide the order of removal of those elements in Priority queue.
The queue (data structure) uses FIFO but the priority queue doesn’t remove it’s elements on basis of their arrivals.
So, now as you’ve learnt the basic definition and terms of Priority queue. Let’s jump deeper and explore some of the operation on Python priority queue. What are some of the main or popular operations performed on priority queue? We can iterate through our priority queue or perform sorting on it. And also one can also change priority of elements in Python priority queue or we will see some operations like Python priority queue decreasing key or updating values.
How Can We Implement Priority Queue in Python
There can be many ways to implement the priority queue in Python. But in this tutorial, we will talk about the best three ways to implement a priority queue in Python.
- Python sorted list
- Using the heapq Module
- Using
queue.PriorityQueue
Implementing Priority Queue Using Sorted List
Let’s start with an effortless and straightforward way. In this way, we will use a standard list, but we need to sort that list every time an item is added.
Let’s walk through an example of a priority queue using lists.
Example 1:
Suppose we want to create a priority queue that stores the order of students who should be let into a seminar first. Then we can use the following code to create a priority queue using lists:
student_pass = []
student_pass.append((3, 'Ram'))
student_pass.append((1, 'Sham'))
student_pass.append((2, 'Vasu'))
# NOTE: Remember to re-sort every time
# a new element is inserted, or use
# bisect.insort().
student_pass.sort(reverse=True)
while student_pass:
item = student_pass.pop()
print(item)
Output:
(1, 'Sham')
(2, 'Vasu')
(3, 'Ram')Time Complexity of Priority Queue Using Sorted List
Maintaining the order by appending to the list and re-sorting also takes at least O(n log n) time. Thus, it is only efficient when we have to make a few insertions.
Implementing Priority Queue Using the heapq Module
Before implementing and jumping directly to the examples. We must know all the building blocks of the structure i.e, Heap, queue, priority queue etc.
What exactly are a heap and priority queue in Python?
So, priority queue is implemented in Python (not only in Python) using Binary Heap or you’d say it heap queue (heapq below in this article).
What is heap(heapq) ?
A Heap is a tree based Data structure also known as heap priority. (In Simple words, you can say priority queue in Python uses heap to classify the elements)
What is a queue ?
A queue of humans, imagine someone holding a premium pass, so he/she will be given more priority over others similarly in Priority Queue.
Firstly let’s implement the priority queue using the heapq module provided by Python itself
import heapq
q = []
heapq.heappush(q, (3, 'A')) #heappush is a method to add an
heapq.heappush(q, (1, 'B')) #element
heapq.heappush(q, (2, 'C'))
while q:
next_item = heapq.heappop(q) #heappop is a method to
print(next_item) #remove an element
Output:
(1, 'B')
(2, 'C')
(3, 'A')You may have came across many questions like min heap and max heap. Or may be you’d have read something like priority queue max size python etc. So here’s the answer to all of these scary questions. Here we are using heapq module/class in Python. Remember, which is default use for min heap. To use it for max heap multiply each element by negative 1 i.e -1
Demonstration of Max heap
#demonstartion of max heap using heapq in python 3
from heapq import heappop, heappush, heapify
# An empty heap has been created
heap = []
heapify(heap)
heappush(heap, -1 * 10) #adding elements using heappush
heappush(heap, -1 * 30) # function by multiplying them with
heappush(heap, -1 * 20) #-1
heappush(heap, -1 * 400)
# printing the value of maximum element
print("Head value of heap : "+str(-1 * heap[0]))
# print all elements in the heap
print("The elements in heap: ")
for i in heap:
print(-1 * i, end = ' ')
print("\n")
element = heappop(heap)
# printing the elements of the heap
print("The heap elements: ")
for i in heap:
print(-1 * i, end = ' ')
#Result of above code after execution
#Head value of heap: 400
#The heap elements :
#400 30 20 10
#The heap elements :
#30 10 20
Time Complexity of heapq
The heapq implementation has O(log n) time for insertion and extraction of the smallest element. Note that heapq only has a min heap implementation, but there are ways to use as a max heap.
Implementing Priority Queue Through queue.PriorityQueue Class
Another way to create a priority queue in Python 3 is by PriorityQueue class provide by Python 3. (you can also use it in Python 2 but sadly Python 2 is no more in the use). And also below code could help you to iterate over priority queue in Python or (some people may call it just ) priority queue in Data structure.
from queue import PriorityQueue
q = PriorityQueue()
q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))
while not q.empty():
next_item = q.get()
print(next_item)
Output:
(1, 'eat')
(2, 'code')
(3, 'sleep')Time Complexity Using queue.PriorityQueue Class
The queue.PriorityQueue uses the same heapq implementation from internally and thus has the same time complexity which is O(log n) . However, it is different in two key ways. Firstly, it is synchronized, so it supports concurrent processes. Secondly, it is a class interface instead of the function based interface of heapq . Thus, queue.PriorityQueue is the classic OOP style of implementing and using Priority Queues.
Another Not Very Popular Method of Priority Queue
There is many methods or ways to implement priority queues in python. One of the not very popular method is by peek implementation which is shown below.
Peek implementation of Priority Queue:
What is peek in Priority queue? So if you use java then peek() is just another method on priority queue which gives you the 1st element of priority queue. But in python 3 as we are learning about priority queue in Python 3, we don’t have any built-in method like peek(). So we have to write it’s implementation.
Here’s is the code for peek in Python priority queue (the below code is executable on Python 3.
import queue
class PeekablePriorityQueue(queue.PriorityQueue):
def peek(self):
"""Peeks the first element of the queue
Returns
-------
item : object
First item in the queue
Raises
------
queue.Empty
No items in the queue
"""
try:
with self.mutex:
return self.queue[0]
except IndexError:
raise queue.Empty
There’s so many more methods or modules or class available in python 3 library you can refer. And so many operations you can perform on priority queue like itrating through it, decrease key, update values, etc
Applications of Priority Queue
Let’s explore the applications of Priority queue:
- Priority queues are used in operating system for giving priority to a important task over other or simply interruption handling.
- In traffic light, depending upon the traffic, the colors will be given priority.
- Implementing Dijkstra’s algorithm through Priority Queue.
- We can sort heaps through priority queues.
- Prim’s algorithm implementation can be done using priority queues.
Must Read:
- How to Convert String to Lowercase in
- How to Calculate Square Root
- User Input | Input () Function | Keyboard Input
- Best Book to Learn Python in 2020
Conclusion
In Python, there are many different ways to implement a priority queue. The two most common options to create a priority queue are to use the heapq module, or to use the queue.PriorityQueue class.
If you have made it to the end, you’re now an expert on the topic of priority queue in Data structure with Python. You can perform all kind of operations on it and use its many of the above mentioned applications in solving problems. Remember to implement your learnings in Python 3 and not other versions like Python 2.
Try to implement the programs on your side and let us know if you have any queries in the comment section below.
Happy Pythoning!