Understanding Python’s Heapq Module: A Guide to Heap Queues

3 min readOct 21, 2023

In the world of data structures, heaps are paramount for maintaining a priority queue. Python’s heapq module provides a fast and efficient implementation of the heap queue algorithm. This article aims to explore the fundamentals of the heapq module, delving into the time complexities of the most common functions, namely heappush and heappop.

Understanding heapq in Python

Heapq is a module in Python that provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It allows for efficient management of priority queues in a way that elements with higher priority are served before elements with lower priority.

Time Complexities of Heappush and Heappop

heappush

Time Complexity: O(log n)

heappop

Time Complexity: O(log n)

Both heappush and heappop functions in Python’s heapq module have a time complexity of O(log n). This time complexity is a result of the underlying data structure used in the heapq module, which is a binary heap.

Understanding the Logarithmic Time Complexity

The logarithmic time complexity is a characteristic feature of binary heaps, which heapq is based on. Binary heaps are binary trees for which every parent node has a value less than or equal to any of its children. This property allows for efficient insertion and deletion operations, resulting in a logarithmic time complexity for heappush and heappop operations.

When elements are added to the heap, the algorithm ensures that the heap property is maintained, which involves comparing and swapping elements at specific positions in the heap. This process is optimized due to the logarithmic nature of the binary heap structure, resulting in the overall time complexity of O(log n) for both heappush and heappop operations.

Understanding Time Complexities in Big O Notation with Examples

Let’s demonstrate the time complexities with Python examples.

Example 1: Using heappush

import heapq

# Creating a simple heap
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print("Heap after push operations:", heap)

Example 2: Using heappop

import heapq

# Creating a simple heap
heap = [4, 1, 7, 3]
# Popping elements from the heap
print("Popped element:", heapq.heappop(heap))
print("Heap after pop operation:", heap)

Integration into Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest paths from a single source to all other vertices in a weighted graph. We can integrate the heapq priority queue into Dijkstra's algorithm to efficiently process nodes based on their distances.

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances
# Example usage
graph = defaultdict(dict)
graph['A']['B'] = 3
graph['A']['C'] = 1
graph['B']['C'] = 7
graph['C']['B'] = 2
graph['C']['D'] = 6
graph['D']['B'] = 2
distances = dijkstra(graph, 'A')
print(distances)

Output:

{'A': 0, 'B': 3, 'C': 1, 'D': 7}

That’s it for this article! Feel free to leave feedback or questions in the comments.

Enjoyed the article and found it helpful? If you’d like to show your appreciation and support my work, you can buy me a coffee! Your support goes a long way in helping me create more content like this. Thank you in advance! ☕️