A queue is a first-in-first-out order (FIFO) , in which items are taken out or accessed on a first-come-first-served basis. An example of a queue would be a line at a movie ticket stand. But, what is a priority queue?
A priority queue in Python is an abstract data structure, or a data structure defined by its behavior, that is like a normal queue but where each item has a special “key” to quantify its priority. For example, if the movie theater decides to serve loyal customers first, it will order them by their loyalty, either by loyalty points or number of tickets purchased. In such a case, the queue for tickets will no longer be first-come-first-served, but most-loyal-first-served. The customers will be the “items” of this priority queue while the “priority” or “key” will be their loyalty.
3 Ways to Build Priority Queues in Python
list: This strategy is efficient if you don’t need to make many insertions.
heapq: This version supports O(logn) time for insertion and the smallest element.
queue.PriorityQueue: This approach supports concurrent processes and it’s a class interface.
Another example is airlines that put luggage on the conveyor belt based on the status or ticket class of the passengers. Baggage tagged with “priority,” “business” or “first-class” usually arrives earlier than other non-tagged baggage.
How to Implement Priority Queues in Python
Consider that we want to have a priority queue of customers based on their loyalty points. The higher the points, the higher their priority. When it comes to implementing priority queues in Python, there are a number of options. We will explore three of them here.
1. Using a
A very simple and straightforward way is to use the normal
list but sort it every time an item is added. Here’s an example:
customers =  customers.append((2, "Harry")) #no sort needed here because 1 item. customers.append((3, "Charles")) customers.sort(reverse=True) #Need to sort to maintain order customers.append((1, "Riya")) customers.sort(reverse=True) #Need to sort to maintain order customers.append((4, "Stacy")) customers.sort(reverse=True) while customers: print(customers.pop(0)) #Will print names in the order: Stacy, Charles, Harry, Riya.
However, it takes
O(n log n) time to maintain the order when an item is added to the list. It’s only efficient when we don’t need to make many insertions.
We can also use the
heapq module in Python to implement our priority queue. This 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 other ways to use a
max heap that we won’t cover in this article.
Here’s an example:
import heapq customers =  heapq.heappush(customers, (2, "Harry")) heapq.heappush(customers, (3, "Charles")) heapq.heappush(customers, (1, "Riya")) heapq.heappush(customers, (4, "Stacy")) while customers: print(heapq.heappop(q)) #Will print names in the order: Riya, Harry, Charles, Stacy.
PriorityQueue uses the same
heapq implementation from the previous example internally so it has the same time complexity. However, it’s different in two key ways. First, it’s synchronized, so it supports concurrent processes. Second, it’s a
class interface as opposed to the
function based interface of
PriorityQueue is the classic object-oriented programming (OOP) style of implementing and using priority queues.
Let’s construct a priority queue for our movie buffs:
from queue import PriorityQueue customers = PriorityQueue() #we initialise the PQ class instead of using a function to operate upon a list. customers.put((2, "Harry")) customers.put((3, "Charles")) customers.put((1, "Riya")) customers.put((4, "Stacy")) while customers: print(customers.get()) #Will print names in the order: Riya, Harry, Charles, Stacy.
And that’s how we can implement priority queues in Python. I hope this article helps you get started with and understand the importance of priority queues.