Python heapq Module: Using heapq to Build Priority Queues in Python

Hello everyone! In today’s article, we’ll be looking at using the Python heapq Module.

This modules gives us a quick and easy way to build any type of priority queue for your application.

To understand more about this module, let’s take a closer look.

Priority Queue as a Min-Heap

A Priority Queue is a queue where elements have another parameter called the priority. Based on the priority of the element, those elements are pushed / popped off the Queue first.

This modules utilizes a binary min-heap for building the priority queue.

The main property of this heap queue data structure is that the smallest element is always popped off first!

In addition, once any element is pushed / popped, the same type of structure is maintained.

This data structure has a large number of applications, including sorting.

Let’s understand how we can now use this module.

Understanding the Python heapq Module

This module is a part of the standard library, so there’s no need to install it separately using pip.

To import the heapq module, we can do the following:

import heapq

In the heapq module, we mainly require 3 methods which we need for building and manipulating our priority queue:

• heappush(heap, item) -> Push item onto the heap, and maintaining the min-heap property.
• heappop(heap) -> Pops and returns the smallest item from the heap. If the heap is empty, we will get an IndexError Exception.
• heapify(iterable) -> Converts the iterable (list, etc) into a min-heap. This modifies the iterable in-place

Let’s take a simple example of building the priority queue from a normal list of integers.

import heapq

a = [1, 4, 3, 5, 2]

print("List =", a)

# Convert the iterable (list) into a min-heap in-place
heapq.heapify(a)

print("Min Heap =", a)

Output

List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]

As you can see, the heapify() method modifies the list in-place, and converts it into a min-heap.

To observe why it is a min-heap, simply draw the tree representation of both the lists.

For a min-heap representation from a list, for a node with index i, its children have indices 2*i and 2*i+1.

For a min-heap, the parent must be lesser than both it’s children!

As you can see, the second list indeed follows our min-heap property! Thus, we have verified that the heapify() method gives us the correct min-heap.

We will now push and pop to/from our heap.

import heapq

a = [1, 4, 3, 5, 2]

print("List =", a)

# Convert the iterable (list) into a min-heap in-place
heapq.heapify(a)

print("Min Heap =", a)

# Use heappush
heapq.heappush(a, 10)

print("After heappush(), Min Heap =", a)

# Use array indexing to get the smallest element
print(f"Smallest element in the heap queue = {a[0]}")

# Use heappop() and return the popped element
popped_element = heapq.heappop(a)

print(f"Popped element = {popped_element}, Min Heap = {a}")

Output

List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]
After heappush(), Min Heap = [1, 2, 3, 5, 4, 10]
Smallest element in the heap queue = 1
Popped element = 1, Min Heap = [2, 4, 3, 5, 10]

As you can see, we were easily able to perform our desired operations on this heap queue! Let’s now look at using this min-heap to sort our list using heapsort.

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        # Push the elements onto the heap
        heapq.heappush(h, value)
    # Keep popping the smallest elements and appending them to our sorted list
    return [heapq.heappop(h) for i in range(len(h))]

sorted_list = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(sorted_list)

Output

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Great! Indeed, we have used the heap queue property to sort our list!

Conclusion

In this article, we learned about using the Python heapq module and saw how we could use the min-heap property to sort our unordered list.

References

• Python Documentation on the heapq module