Python Priority Queue Example
A “Priority Queue” is a queue type that orders/sorts its elements according to their importance. It is used in various applications such as scheduling, graph algorithms, and simulation that require processing tasks in order of priority. There are different methods in Python, such as heapq, queue, and others, that are used to implement a priority queue.
This Python tutorial presents a comprehensive guide on Priority Queue using numerous examples.
What is Priority Queue in Python?
A Priority Queue is an abstract data type that organizes elements in a sequence based on their assigned priorities. It is a data structure that removes the element with the highest priority first, while a regular queue removes elements in the order in which they were inserted.
How to Implement Priority Queues in Python?
The following methods are used to implement Priority Queues in Python:
Method 1: Implementing Priority Queues Using List
The list is used to implement a Priority Queue in Python. The list allows us to append elements and then sort them based on their priority. Here is an example:
students.append((1, "Joseph"))
students.append((4, "Lily"))
students.sort(reverse=True)
students.append((3, "Anna"))
students.sort(reverse=True)
students.append((2, "Henry"))
students.sort(reverse=True)
while students:
print(students.pop())
In the above code:
- The list named “students” is declared at the start.
- The “append()” function is used multiple times to insert the specified data at a particular index to the list.
- The element value is added to the list in random order.
- To implement a priority queue, the “sort()” method is utilized to sort the list in ascending order after adding an element to the list.
- The “while” loop and the “pop()” function are used to display the list element in ascending order.
Output
The list has been sorted based on the highest priority.
Method 2: Implementing Priority Queues Utilizing heapq Module
In Python, the “heapq” module can also be utilized to execute a priority queue. It uses a binary heap to maintain the priority order of elements. Let’s explore this via the following code:
students = []
heapq.heappush(students, (3, "Joseph"))
heapq.heappush(students, (1, "Lily"))
heapq.heappush(students, (4, "Henry"))
heapq.heappush(students, (2, "Anna"))
while students:
print(heapq.heappop(students))
In the above code:
- The “heapq” module is imported, and the list named “students” is initialized.
- The “heapq.heappush()” function is used to add some element value to the list in random order.
- The while loop is employed to iterate through/over the list.
- Inside the while loop, the “heapq.heappop()” function removes and returns the list element in ascending order.
Output
Method 3: Implementing Priority Queues Using queue.PriorityQueue
The “PriorityQueue” class of the “queue” module is used to implement the Priority Queue in Python. Here’s an example of this method:
students = queue.PriorityQueue()
students.put((3, "Henry"))
students.put((4, "Lily"))
students.put((1, "Joseph"))
students.put((2, "Anna"))
while not students.empty():
print(students.get())
In the above code:
- The “queue” module is imported.
- The “queue.PriorityQueue()” creates an empty priority queue object.
- The “students.put()” function is used to insert specified element values into the list.
- The “while” loop is utilized to iterate through/over the list and print the list element in ascending order using the “get()” function.
Output
Conclusion
In Python, the “List”, “heapq”, and “queue.PriorityQueue” methods are used to implement Priority Queues and return data items based on their priority. The list is used to implement the priority queues by sorting the list element every time an item is added. The “heapq” module and the “queue.PriorityQueue()” class of the queue module can implement the priority queue. This guide delivered an in-depth guide on priority queues using numerous examples.
Source: linuxhint.com