Introduction to Priority Queues in Python

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.

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.

More on Software Engineering: Time Complexity: What Developers Need to Know

1. Using a LIST

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.

2. Using HEAPQ

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.

More on Data: Sorting Algorithms: Slowest to Fastest

3. Using QUEUE.PRIORITYQUEUE

The 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 heapq. Thus, 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.