How to Implement Priority Queue in Python: Simple Guide

In Python, you can implement a priority queue using the built-in heapq module, which provides functions to maintain a heap data structure. Use heapq.heappush() to add items and heapq.heappop() to remove the smallest priority item efficiently.

Syntax

The heapq module uses a list to represent a heap. The main functions are:

• heapq.heappush(heap, item): Adds item to the heap.
• heapq.heappop(heap): Removes and returns the smallest item from the heap.

The heap list must be maintained only by these functions to keep the priority queue properties.

python

import heapq

heap = []  # empty list to hold the heap
heapq.heappush(heap, 10)  # add item with priority 10
heapq.heappush(heap, 5)   # add item with priority 5
smallest = heapq.heappop(heap)  # removes and returns 5
print(smallest)

Output

5

Example

This example shows how to create a priority queue, add items with different priorities, and pop them in order of priority (lowest first).

python

import heapq

# Create an empty priority queue
priority_queue = []

# Add items with priorities
heapq.heappush(priority_queue, (3, 'Clean the house'))
heapq.heappush(priority_queue, (1, 'Do homework'))
heapq.heappush(priority_queue, (2, 'Buy groceries'))

# Pop items by priority
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"Priority {priority}: {task}")

Output

Priority 1: Do homework
Priority 2: Buy groceries
Priority 3: Clean the house

Common Pitfalls

Common mistakes when using heapq include:

• Modifying the heap list directly instead of using heappush and heappop, which breaks the heap property.
• Forgetting that heapq is a min-heap, so the smallest item has the highest priority.
• Not using tuples for complex priorities, which can cause incorrect ordering.

To fix these, always use heappush and heappop, and use tuples like (priority, item) to define priority clearly.

python

import heapq

heap = [10, 5, 20]
# Wrong: modifying list directly
heap.append(1)
# This breaks the heap property
print(heap)  # Output is not a valid heap

# Right way:
heapq.heapify(heap)  # fixes the heap
heapq.heappush(heap, 1)
print(heap)

Output

[10, 5, 20, 1]
[1, 5, 20, 10]

Quick Reference

Summary of key heapq functions for priority queues:

Function	Description
heapq.heappush(heap, item)	Add an item to the heap maintaining heap property
heapq.heappop(heap)	Remove and return the smallest item from the heap
heapq.heapify(list)	Convert a list into a heap in-place
heapq.heappushpop(heap, item)	Push item then pop and return smallest item
heapq.heapreplace(heap, item)	Pop smallest item, then push new item

Key Takeaways

Use the heapq module to implement priority queues efficiently in Python.

Always use heappush and heappop to maintain the heap property correctly.

heapq implements a min-heap, so smaller values have higher priority.

Use tuples (priority, item) to handle complex priority sorting.

Avoid modifying the heap list directly; use heapq functions instead.