Python Priority Queue: A Guide

Python Priority Queue: A Guide

A Python priority queue stores data in a particular order. There are two ways to implement a priority queue in Python: using the queue class and using the heapq module.

You may want to order data based on the values of each item in the list. For instance, you may want the highest value to appear first in the list, and the lowest value to appear last in the list.

That’s where priority queues come in. A priority queue is a data structure that stores data based on the value of its keys in ascending order. This allows you to easily access the smallest and largest value in the queue.

This tutorial will discuss why you should not use a list to create priority queues. We will show you two more efficient approaches you can use to create a Python priority queue.

What is a Python Priority Queue?

Priority queues are a modified version of a queue that stores data in order of which element has the highest priority. The priority of each element in a priority queue is decided depending on the value of the element.

In computer science, queues are data structures that store items in the first-in, first-out (FIFO) order. There are a few scenarios where using this structure can be helpful.

For instance, suppose you are building an order tracking app for a restaurant. The person who places an order first should be served before the people who place their order next. To keep track of orders, you would want to use a queue.

There are two ways to define a priority queue in Python:

• Using the PriorityQueue queue class
• Using the heapq module

You can define a priority queue using a list structure. But, this strategy is less efficient than using the PriorityQueue queue class or the heapq module.

Priority Queue Python: queue.PriorityQueue

The queue.PriorityQueue class creates a Python priority queue. This class is part of the Python queue library. You need to import the queue library to use this class. To retrieve an item from a PriorityQueue, you can use the get() method.

To access the PriorityQueue class, we need to import it into our code, which we can do using this Python import statement:

from queue import PriorityQueue

Suppose we want to create a priority queue for ticket holders at a local concert. We could do so using this code:

from queue import PriorityQueue

ticket_holders = PriorityQueue()

ticket_holders.put((3, 'Paul'))
ticket_holders.put((1, 'Miles'))
ticket_holders.put((2, 'Dani'))

while not ticket_holders.empty():
	item = ticket_holders.get()
	print(item)

Our code returns:

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

In our code, we first import the PriorityQueue class from the queue library, then we initialize a priority queue called ticket_holders. Next, we insert three tuples into our priority queue, which store the ticket numbers and names associated with a ticket.

We use a Python while loop to run through each item in the ticket_holders priority queue. Then, we retrieve that item using get().

The queue.PriorityQueue method is efficient and easy to use, which makes it a great choice for when you need to create a priority queue.

Priority Queue Python heapq Module

The heapq module lets you define a Python priority queue. A heapq data structure removes items in order of their priority. The lowest value has the lowest priority and he highest value has the highest priority in the heapq structure.

Before we can use the heapq module, we must first import it into our code using the following import statement:

import heapq

Let’s return to our earlier example. Suppose we want to create a priority queue to store information about ticket holders at a concert. We could do so using the heapq module and this program:

import heapq

ticket_holders = []

heapq.heappush(ticket_holders, (3, 'Paul'))
heapq.heappush(ticket_holders, (1, 'Miles'))
heapq.heappush(ticket_holders, (2, 'Dani'))

while ticket_holders:
	item = heapq.heappop(ticket_holders)
	print(item)

Our code returns:

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

First, we imported the heapq library, and then we initialized a Python variable called ticket_holders. We used the heappush() method to push three tuples to our priority queue. This queue stores the ticket numbers for each ticket holder and the name of each ticket holder.

We then created a while loop which loops through each item in our priority queue. This loop removes the item at the top of the queue using heappop(). Then, the removed item is printed to the console. As you can see, all the items in our queue are printed out in order of their priority.

Why You Should Not Keep a List

Technically, you can create a priority queue using the Python list data structure. To do so, you would create a list, then order it in ascending order.

However, this is a relatively inefficient way of maintaining a priority queue. As you change items in the list, you would need to re-order the list, which takes up time.

You can use a traditional list as a priority queue if you only need to store a few values. But, if you are looking to create a larger queue, lists are not a good option.

For reference, let’s walk through an example of a priority queue using lists. Suppose we want to create a priority queue that stores the order of ticket holders who should be let into a concert first. We could use the following code to create this queue:

ticket_holders = []

ticket_holders.append((3, 'Paul'))
ticket_holders.append((1, 'Miles'))
ticket_holders.append((2, 'Dani'))

ticket_holders.sort(reverse=True)

while ticket_holders:
	item = ticket_holders.pop()
	print(item)

Our code returns:

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

We have created a list called ticket_holders, then we added three tuples to the list. Each tuple contained the ticket number of a ticket holder and their name. Then, we used the Python sort() function to sort our list of ticket holders in reverse order.

We created a while loop that iterates through every item in the ticket_holders list and the item at the top of the list. Then, our code prints out the removed item to the console.

Conclusion

The two most common to create a priority queue are to use the heapq module or the queue.PriorityQueue class. While you can technically use a list as a priority queue, this approach does not scale well.

This tutorial discussed, with reference to examples, how to create a priority queue in Python. Now you’re equipped with the knowledge you need to start creating your own priority queues like a Python professional!

For more guidance on how to learn Python, check out our complete How to Learn Python guide.