In this Python article, I will explain priority queue in Python and how they work and provide detailed examples of their usage in Python.
Additionally, I will also explain what is the max priority queue in Python.
Priority queues are a fundamental data structure in computer science used to manage elements with associated priorities.
Unlike traditional queues, where elements are processed in a first-in-first-out (FIFO) order, priority queues process elements based on their priority, with higher-priority elements processed before lower-priority ones.
In Python, priority queues are commonly implemented using the heapq module or external libraries such as the queue.PriorityQueue.
What is the priority queue in Python?
A priority queue in Python is a data structure that stores elements and their respective priorities, where the priority determines the order in which elements are processed.
Elements with higher priority are processed before elements with lower priority, regardless of the order in which they were added.
How Python priority queues work
Priority queues in Python can be implemented using underlying data structures, such as heaps or balanced trees. The most common implementation is using a heap data structure due to its efficiency in maintaining the highest (or lowest) priority element at the top.
In Python, the heapq module provides functions for implementing heaps, which can be used to create a priority queue. The heapq module maintains a list as a heap, where the first element is always the smallest (or largest, depending on the implementation) element.
There are other ways as well. Here is the list that we will see in this article:
- heapq module
- queue.PriorityQueue class
- Using a Sorted List
Let’s see them all in detail with examples:
1. Python priority queue with heapq module
The heapq module in Python provides functions for heap operations, allowing efficient implementation of priority queues. It includes functions like heappush() to add elements and heappop() to remove the smallest element.
Let’s see an instance:
import heapq
pq = []
def add_task(task, priority):
heapq.heappush(pq, (priority, task))
def get_highest_priority_task():
if pq:
return heapq.heappop(pq)[1]
else:
return None
add_task('Task 1', 3)
add_task('Task 2', 1)
add_task('Task 3', 2)
print(get_highest_priority_task())
print(get_highest_priority_task())
print(get_highest_priority_task())
The add_task(task, priority) function is defined to add a task to the priority queue in Python with the specified priority. We use the heapq.heappush() to maintain the heap property, to ensure that the task with lower priority values is closer to the front of the queue.
def add_task(task, priority):
heapq.heappush(pq, (priority, task))
The get_highest_priority_task() function gives back and removes the task with the highest priority from the Python priority queue. This uses heapq.heappop() to extract the task with the smallest priority value efficiently. If the queue is empty, it returns None.
def get_highest_priority_task():
if pq:
return heapq.heappop(pq)[1]
else:
return None
Output:
Task 2
Task 3
Task 1
The output can be seen in the screenshot below after executing the code in PyCharm.
2. Priority queue in Python inbuilt queue.PriorityQueue class
The queue.PriorityQueue class in Python provides an implementation of a priority queue in Python. It internally uses a heap data structure to maintain the queue efficiently. The elements in the queue are tuples of the form (priority, item).
Here’s an example demonstrating the usage of a queue.PriorityQueue in Python:
from queue import PriorityQueue
pq = PriorityQueue()
def add_task(task, priority):
pq.put((priority, task))
def get_highest_priority_task():
if not pq.empty():
return pq.get()[1]
else:
return None
add_task('California Data Processing', 3)
add_task('New York Data Analysis', 1)
add_task('Texas Data Entry', 2)
print(get_highest_priority_task())
print(get_highest_priority_task())
print(get_highest_priority_task())
I have created a function named “add_task(task, priority)” that adds a task to the priority queue with the specified priority. It takes two parameters.
The functions add the task to the priority queue in Python using the put() method of the PriorityQueue class, with the priority specified as a tuple along with the task.
def add_task(task, priority):
pq.put((priority, task))
I have also created another function in Python named “get_highest_priority_task()” that gives and removes the highest priority task from the priority queue. This checks if the priority queue is not empty using the empty() method of the PriorityQueue class.
If the queue is not empty, it retrieves the top item using the get() method, which returns a tuple(priority, task). The function returns only the task (index 1 of the tuple) without the priority in Python.
def get_highest_priority_task():
if not pq.empty():
return pq.get()[1]
else:
return None
Output:
New York Data Analysis
Texas Data Entry
California Data Processing
The screenshot below shows the code implemented in the PyCharm editor.
3. How to use priority queues in Python in a list
To implement a priority queue in Python in a list, we have to declare an empty Python list into which elements are inserted using the append() method of the list class. The list is then sorted in ascending order. The While loop retrieves the elements using the pop() method.
Let’s examine a simple instance:
employee = []
employee.append((5, 'Nick'))
employee.append((1, 'Rohan'))
employee.append((3, 'Jack'))
employee.sort(reverse=True)
while employee:
employee_tuple = employee.pop()
print(employee_tuple)
After writing the above code (Python priority queue implementation), the element sorts and dequeues elements based on their Python priority queue.
Output:
(1, 'Rohan')
(3, 'Jack')
(5, 'Nick')
You can refer to the screenshot below for Python priority queue implementation.
Max priority queue in Python
Now, let us understand the max priority queue in Python.
In the Python max priority queue, the list will be arranged in descending order of their priority. The While loop retrieves the elements using the pop(0) method.
Consider the following example:
employee = []
employee.append((5, 'Nick'))
employee.append((1, 'Ross'))
employee.append((3, 'Jack'))
employee.sort(reverse=True)
while employee:
employee_tuple = employee.pop()
print(employee_tuple)
After writing the above code (max priority queue in Python), the list is sorted in descending order and dequeue elements based on their priority queue.
Output:
(1, 'Ross')
(3, 'Jack')
(5, 'Nick')
You can refer to the screenshot below for the max priority queue in Python.
Conclusion
Python priority queues are an essential data structure for managing elements with associated priorities.
Understanding what a priority queue in Python is and how they work with different implementation techniques like the heapq module or the queue.PriorityQueue class, one can easily handle the program based on their priorities.
You may also like to read the following article in Python:
- Python 3 pickle typeerror, a bytes-like object is required, not ‘str’
- Python exit command (quit(), exit(), sys.exit())
- Python input and raw_input function
I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.