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