Python - Python heapq Module and Priority Queue Implementation

The Python heapq module provides functions for working with heaps, which are specialized tree-based data structures commonly used to implement priority queues. A priority queue is a data structure where each element is associated with a priority, and the element with the highest priority is processed before elements with lower priority. In Python's heapq implementation, the smallest element has the highest priority by default. Unlike a traditional tree structure, a heap is usually stored efficiently inside a Python list.

What Is a Heap?

A heap is a complete binary tree that follows a specific ordering rule. Python's heapq module implements a min-heap, where the smallest element is always located at the first position of the list.

For example:

import heapq

numbers = [30, 10, 20, 5, 15]
heapq.heapify(numbers)

print(numbers)

The resulting list represents a valid heap. The important point is that numbers[0] will always contain the smallest element. The entire list does not need to be sorted.

A min-heap follows the rule that every parent node is less than or equal to its child nodes. Because of this property, the smallest element can be accessed efficiently without sorting the entire collection.

Creating a Heap with heapify()

The heapify() function converts an existing list into a heap.

import heapq

numbers = [40, 10, 30, 5, 20]

heapq.heapify(numbers)

print(numbers)

The operation modifies the original list rather than creating a new heap object.

The major advantage of heapify() is its efficiency. It can transform an unordered list into a valid heap in O(n) time, where n is the number of elements.

After heapification, you can use other heapq functions such as heappush() and heappop() to maintain the heap.

Adding Elements with heappush()

The heappush() function adds an element to an existing heap while preserving the heap property.

import heapq

numbers = [10, 20, 30]
heapq.heapify(numbers)

heapq.heappush(numbers, 5)

print(numbers)

The new element is inserted into the appropriate position internally. You do not need to manually rearrange the list.

The operation generally takes O(log n) time because the new element may need to move upward through the heap until the heap property is restored.

Removing Elements with heappop()

The heappop() function removes and returns the smallest element from the heap.

import heapq

numbers = [10, 20, 30, 5, 15]
heapq.heapify(numbers)

smallest = heapq.heappop(numbers)

print("Removed:", smallest)
print("Heap:", numbers)

The smallest value is removed first. After removal, heapq reorganizes the remaining elements to maintain the heap property.

This operation takes O(log n) time.

Repeated calls to heappop() can therefore be used to process elements in increasing priority order:

import heapq

numbers = [40, 10, 30, 5, 20]

heapq.heapify(numbers)

while numbers:
    print(heapq.heappop(numbers))

The output will contain the values from smallest to largest.

Viewing the Smallest Element

If you only want to see the smallest element without removing it, you can access the first element of the list:

import heapq

numbers = [25, 10, 30, 5, 15]
heapq.heapify(numbers)

print(numbers[0])

Here, numbers[0] contains the smallest element.

This is an O(1) operation because the smallest element is always stored at the root of the heap.

Using heappushpop()

Python also provides heappushpop(), which combines pushing a new value and popping the smallest value.

import heapq

numbers = [10, 20, 30]
heapq.heapify(numbers)

result = heapq.heappushpop(numbers, 5)

print("Returned:", result)
print("Heap:", numbers)

This can be more efficient than separately performing heappush() followed by heappop() when both operations are required.

Using heapreplace()

The heapreplace() function removes the smallest element and then inserts a new element.

import heapq

numbers = [10, 20, 30]
heapq.heapify(numbers)

result = heapq.heapreplace(numbers, 25)

print("Removed:", result)
print("Heap:", numbers)

The important difference between heappushpop() and heapreplace() is the order in which the operations conceptually occur.

heappushpop() first considers the new element along with the existing heap and returns the smallest value.

heapreplace() removes the current smallest value first and then inserts the new value.

Implementing a Priority Queue

One of the most important applications of heapq is implementing a priority queue.

Suppose a hospital needs to process patients according to priority. A smaller priority number can represent a more urgent case.

import heapq

patients = []

heapq.heappush(patients, (1, "Emergency Patient"))
heapq.heappush(patients, (3, "Regular Patient"))
heapq.heappush(patients, (2, "Urgent Patient"))

while patients:
    priority, patient = heapq.heappop(patients)
    print(priority, patient)

Because tuples are compared starting with their first element, the patient with priority 1 is processed first, followed by priority 2, and then priority 3.

This makes heapq useful for scheduling systems, task management, event processing, and other applications where items need to be handled according to priority.

Priority Queue with Multiple Values

A priority queue can store more information along with the priority.

import heapq

tasks = []

heapq.heappush(tasks, (2, "Send email", "Medium"))
heapq.heappush(tasks, (1, "Fix server", "Critical"))
heapq.heappush(tasks, (3, "Update documentation", "Low"))

while tasks:
    priority, task, importance = heapq.heappop(tasks)
    print(task, importance)

The first tuple element determines the processing order, while the other elements contain additional information.

For more complex objects, it is often useful to include a unique counter or another comparison-friendly value to avoid problems when two priorities are equal.

Finding the Smallest and Largest Values

The heapq module also provides nsmallest() and nlargest().

import heapq

numbers = [45, 12, 78, 23, 9, 56, 31]

print(heapq.nsmallest(3, numbers))
print(heapq.nlargest(3, numbers))

The first statement finds the three smallest values, while the second finds the three largest values.

These functions are useful when you need only a small number of extreme values rather than sorting the complete list.

Time Complexity

Understanding the efficiency of heap operations is important:

This efficiency is one reason heaps are preferred over repeatedly sorting a list when elements are continuously added and removed according to priority.

Heap vs Sorted List

A heap and a sorted list serve different purposes.

A sorted list keeps all elements in sorted order, whereas a heap guarantees only the ordering needed to efficiently access the smallest element.

For example:

numbers = [5, 10, 15, 20, 30]

This is completely sorted.

A heap might look like:

[5, 10, 15, 20, 30]

but the remaining elements do not necessarily appear in complete sorted order for larger or more complex inputs. The important guarantee is that the smallest element is at index 0.

Therefore, if you repeatedly need the smallest item while adding new items, heapq is generally more appropriate than repeatedly sorting the entire list.

Practical Applications

The heapq module is useful in many real-world programming situations. It can be used for priority-based task scheduling, CPU task management, network packet processing, event simulation, shortest-path algorithms, job scheduling, finding the smallest or largest values, and managing queues where items have different priorities.

For example, algorithms such as Dijkstra's shortest-path algorithm commonly use a priority queue to select the next node with the smallest current distance.

Conclusion

Python's heapq module provides an efficient way to work with heap-based data structures and priority queues. It uses a regular Python list internally while maintaining the heap property through specialized operations. The most important functions are heapify(), heappush(), heappop(), heappushpop(), heapreplace(), nsmallest(), and nlargest().

The key concept to remember is that Python's heapq implements a min-heap, so the smallest element is always readily available at the beginning of the heap. This makes it particularly useful whenever a program repeatedly needs to select and process the next item according to priority.