# Python Tutorial: Creating a Priority Queue in Python

## Introduction

In computer science, a priority queue is an abstract data type that is similar to a regular queue or stack, but each element in the queue has a priority associated with it. Elements with higher priority are dequeued first, while those with lower priority are dequeued later. Priority queues are commonly used in algorithms such as Dijkstra’s shortest path algorithm and Huffman coding.

In Python, we can implement a priority queue using the heapq module. The heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

In this tutorial, we will walk through how to create a priority queue in Python using a variety of methods.

## Implementing a Priority Queue in Python

Priority Queue is a data structure that stores a collection of elements and each element has a priority associated with it. The elements are stored based on their priorities and not in the order they are inserted. In this tutorial, we will discuss three different ways to implement a Priority Queue in Python.

### Using a List

One way to implement a priority queue in Python is by using a list. We can insert elements into the list in their respective order of priority and then pop elements from the beginning of the list. To implement this, we can use the insert() method to insert an element at its correct position and the pop() method to remove the element with the highest priority.

Here’s an example:


queue = []

def enqueue(item, priority):
queue.append((priority, item))
queue.sort(reverse=True)

def dequeue():
if not queue:
return None
return queue.pop()[1]


In this code, we define an empty list called queue and two functions enqueue() and dequeue(). The enqueue() function takes two arguments – an item and its priority. It appends a tuple containing both values to the queue list and sorts it in reverse order based on the priorities. The dequeue() function removes and returns the item with the highest priority.

However, using a list for implementing a Priority Queue can be inefficient for large datasets since sorting takes O(n log n) time complexity.

### Using the heapq Module

The heapq module provides an implementation of heap queue algorithm which is used to create a Priority Queue. Heap data structure is binary tree where each node has a parent node and at most two child nodes. In Python, heap is implemented as an array.

Here’s an example:


import heapq

queue = []

def enqueue(item, priority):
heapq.heappush(queue, (priority, item))

def dequeue():
if not queue:
return None
return heapq.heappop(queue)[1]


In this code, we import the heapq module and define an empty list called queue and two functions enqueue() and dequeue(). The enqueue() function takes two arguments – an item and its priority. It uses the heappush() method to insert the tuple containing both values into the heap. The dequeue() function removes and returns the item with the highest priority using the heappop() method.

Using the heapq module is more efficient than using a list since inserting an element into a heap takes O(log n) time complexity.

### Using the queue Module

The queue module provides a PriorityQueue class that can be used to implement a Priority Queue in Python. This implementation is thread-safe, which means it can be used in a multi-threaded environment.

Here’s an example:


import queue

queue = queue.PriorityQueue()

def enqueue(item, priority):
queue.put((priority, item))

def dequeue():
if not queue:
return None
return queue.get()[1]


In this code, we import the queue module and create an instance of the PriorityQueue class called queue. We define two functions – enqueue() and dequeue(). The enqueue() function takes two arguments – an item and its priority. It uses the put() method to insert the tuple containing both values into the Priority Queue. The dequeue() function removes and returns the item with the highest priority using the get() method.

Using the queue module is more efficient than using a list for large datasets since it uses heap data structure internally which has O(log n) time complexity for inserting elements.

## Examples of Priority Queue Use Cases

Priority queues are an important data structure in computer science that allow us to efficiently manage and process data based on priority. They are used in a wide range of applications, including:

Job Scheduling: In many systems, there are multiple jobs that need to be executed, but some jobs have higher priority than others. For example, in an operating system, the kernel needs to schedule tasks for the CPU to execute. Some tasks may be more urgent than others and need to be executed before other tasks in order to maintain system stability and performance.

Load Balancing in Distributed Systems: In a distributed system, there are multiple nodes that work together to accomplish a task. Some nodes may have more resources than others, so it is important to balance the workload across all nodes. A priority queue can be used to manage incoming requests and assign them to nodes based on their current workload and available resources.

Network Packet Scheduling: In network communication, packets of data are sent between devices. However, not all packets have equal importance or urgency. Some packets may contain critical information that needs to be delivered immediately, while others can wait. A priority queue can be used to manage the order in which packets are sent and received based on their priority level.

These are just a few examples of how priority queues can be used in real-world applications. By using Python’s built-in heapq module or third-party libraries like queue.PriorityQueue, we can easily implement a priority queue and use it to manage data based on priority.

## Conclusion

In this tutorial, we learned about priority queues and how to create them in Python. We discussed the basic concepts of priority queues and their implementation using the heapq module.

We started by introducing the concept of priority queues, which are data structures that allow us to store items with priorities and retrieve them in a specific order. We then discussed the different ways of implementing priority queues, such as using arrays or linked lists.

We focused on implementing a priority queue using the heapq module, which is a built-in module in Python that provides functions for implementing heaps. We saw how we can use the heappush() function to add items to the heap and heappop() function to remove items from the heap.

We also discussed how we can use a tuple to represent an item in the heap, where the first element of the tuple represents its priority and the second element represents its value. This allows us to easily compare items based on their priorities.

Finally, we implemented a simple example of a priority queue using heapq module. We created a list of tuples representing items with their priorities and used heappush() and heappop() functions to add and remove items from the queue respectively.

Overall, priority queues are useful data structures that can be used in many applications such as task scheduling, job management, and network routing. With Python’s heapq module, it is easy to implement priority queues in your programs.
Interested in learning more? Check out our Introduction to Python course!

Your FREE Guide to Become a Data Scientist

Discover the path to becoming a data scientist with our comprehensive FREE guide! Unlock your potential in this in-demand field and access valuable resources to kickstart your journey.

##### Pierian Training
Pierian Training is a leading provider of high-quality technology training, with a focus on data science and cloud computing. Pierian Training offers live instructor-led training, self-paced online video courses, and private group and cohort training programs to support enterprises looking to upskill their employees.

## You May Also Like

### Guide to NLTK – Natural Language Toolkit for Python

Introduction Natural Language Processing (NLP) lies at the heart of countless applications we use every day, from voice assistants to spam filters and machine translation. It allows machines to understand, interpret, and generate human language, bridging the gap between humans and computers. Within the vast landscape of NLP tools and techniques, the Natural Language Toolkit […]

### GridSearchCV with Scikit-Learn and Python

Introduction In the world of machine learning, finding the optimal set of hyperparameters for a model can significantly impact its performance and accuracy. However, searching through all possible combinations manually can be an incredibly time-consuming and error-prone process. This is where GridSearchCV, a powerful tool provided by Scikit-Learn library in Python, comes to the rescue. […]

### Plotting Time Series in Python: A Complete Guide

Introduction Time series data is a type of data that is collected over time at regular intervals. It can be used to analyze trends, patterns, and behaviors over time. In order to effectively analyze time series data, it is important to visualize it in a way that is easy to understand. This is where plotting […]