Log In

Implementing a Priority Queue in Python

Implementing a Priority Queue in Python
Reading time: 5 min
Hostman Team
Technical writer

A priority queue is a special type of queue where each element is associated with a priority. In a priority queue, elements are dequeued in order of their priority, rather than their insertion order. This makes priority queues a powerful data structure for scenarios where elements with higher priorities need to be processed first.

Importance of Priority Queues in Programming

Priority queues are widely used in various programming applications, including:

  • Task scheduling in operating systems

  • Managing the order of events in simulations

  • Implementing Dijkstra's algorithm for finding the shortest path in graphs

  • Managing a to-do list where tasks have different levels of urgency

Implementing a Priority Queue Using heapq

Python provides a built-in library called heapq that can be used to implement priority queues. The heapq module offers an efficient way to maintain a heap, which is a binary tree where the parent node is always smaller than or equal to its child nodes (min-heap).

Basic Operations: Push, Pop, Peek

Let's explore the basic operations of a priority queue using the heapq module.

Pushing an Element

To add an element to the priority queue, use the heappush function:

import heapq

# Create an empty priority queue
priority_queue = []

# Add elements to the priority queue
heapq.heappush(priority_queue, (2, 'task 2'))
heapq.heappush(priority_queue, (1, 'task 1'))
heapq.heappush(priority_queue, (3, 'task 3'))




Popping an Element

To remove and return the smallest element from the priority queue, use the heappop function:

smallest_task = heapq.heappop(priority_queue)


82d536c3 E66f 4397 810d 0ef2636f4b85

Peeking at the Smallest Element

To look at the smallest element without removing it, simply access the first element of the list:

# Peek at the smallest element
smallest_task = priority_queue[0]


Fd334278 B8cd 4dec A075 0bd06b53ef18

Example Use Cases for Priority Queues

Let's look at different use cases for priority queues.

Task Scheduling

In task scheduling, tasks with higher priorities should be executed before those with lower priorities. A priority queue can manage the order of task execution efficiently.

import heapq

tasks = []

# Add tasks with priorities
heapq.heappush(tasks, (1, 'write report'))
heapq.heappush(tasks, (3, 'email team'))
heapq.heappush(tasks, (2, 'prepare presentation'))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'Executing: {task}')


Ce6078dc 7694 42a3 8ee1 1239b1f14112

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph. A priority queue is used to select the next node to process based on the shortest known distance.

import heapq

def dijkstra(graph, start):
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)],

distances = dijkstra(graph, 'A')


Efb44852 0a8e 4faa B356 604eda8a5fb0

Advanced Priority Queue Operations

In this section, we will look closer at advanced usage of priority queues.

Updating an Element's Priority

Updating an element's priority involves removing the element and adding it again with the new priority. This can be inefficient, but it's a necessary step since heapq does not support direct priority updates.

import heapq

priority_queue = [(2, 'task 2'), (1, 'task 1'), (3, 'task 3')]

# Remove task 2 and add it with a new priority
priority_queue = [(p, t) for p, t in priority_queue if t != 'task 2']
heapq.heappush(priority_queue, (4, 'task 2'))



E15df7a3 F0d4 4cba B069 91edfeb4f0c2

Merging Two Priority Queues

To merge two priority queues, use the heapq.merge function, which returns an iterator over the sorted values.

import heapq

pq1 = [(1, 'task 1'), (3, 'task 3')]
pq2 = [(2, 'task 2'), (4, 'task 4')]

merged_pq = list(heapq.merge(pq1, pq2))


8f0cb6f9 5feb 42cd 8fe4 66c6088ce7d8

Practical Code Examples

Priority Queue with Custom Objects

You can use custom objects in a priority queue by implementing comparison methods.

import heapq

class Task:
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description

    def __lt__(self, other):
        return self.priority < other.priority

priority_queue = []
heapq.heappush(priority_queue, Task(2, 'task 2'))
heapq.heappush(priority_queue, Task(1, 'task 1'))
heapq.heappush(priority_queue, Task(3, 'task 3'))

while priority_queue:
    task = heapq.heappop(priority_queue)



Using Priority Queue in a Multi-threaded Environment

Python's queue.PriorityQueue is a thread-safe priority queue that can be used in multi-threaded applications.

import threading
import queue

def worker(task_queue):
    while not task_queue.empty():
        priority, task = task_queue.get()
        print(f'Processing {task}')

task_queue = queue.PriorityQueue()
task_queue.put((2, 'task 2'))
task_queue.put((1, 'task 1'))
task_queue.put((3, 'task 3'))

threads = []
for i in range(3):
    thread = threading.Thread(target=worker, args=(task_queue,))

for thread in threads:



0b1e61bc Dbf4 4b1c 9dec 9bcba64a99bb


Priority queues are essential for efficiently managing tasks and resources based on priority. Python's heapq and queue.PriorityQueue modules provide powerful tools to implement and manipulate priority queues. Whether for simple tasks or complex algorithms like Dijkstra's, understanding how to use priority queues effectively can significantly enhance your programming toolkit.

For further reading and additional resources, consider the following: