Table of contents
1.
Introduction
2.
Operations using Heapq
2.1.
1. heapify
2.2.
2. heappop
2.3.
3. heappush
2.4.
4. heapreplace
2.5.
5. heappushpop
2.6.
6. nlargest and nsmallest
3.
Common Use-cases and applications of Python Heapq
4.
Finding the Largest and Smallest Elements from a Heap in Python
4.1.
Implementation
5.
Advantages of Using heapq Module in Python
6.
Disadvantages of Using heapq Module in Python
7.
Frequently Asked Questions
7.1.
How are max heaps implemented using the heapq Python module?
7.2.
Is heapq faster than PriorityQueue?
7.3.
Is heapq part of Python's standard library?
7.4.
Does heapq work with strings?
8.
Conclusion
Last Updated: Oct 9, 2024
Easy

Heapq module in Python

Author Dhruv Sharma
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Heaps are a set of concrete data structures implementations for use-cases. It is always required to retrieve the smallest, largest element (or any other sort of priority criteria relevant there). But one can contemplate and debate that it can efficiently do this by sorting all elements in ascending/descending order and retrieving the min/max elements required each time. Still, what happens when one needs to also insert multiple elements after removals/retrievals? For that, one would need to resort the elements to maintain that required order; one can now easily understand how inefficient that would be for solving use-cases such as keeping track of queues of long-running processes/tasks and maintaining an order of priority there, maintaining a set of most recent logs in a system and keeping track of changes etc. it can solve all types of such a wide range of challenges and various problems by using heaps and priority queues.

Heapq module in Python

Let's understand these functionalities with helpful examples covered in the article.

Also See, Intersection in Python, Swapcase in Python

Operations using Heapq

In Python, the heapq module offers various operations for initialisation, insertions and retrievals in the heap. The functions in heapq are all operations that can be performed on lists in Python directly and do not require a custom implementation of a class to be utilised. One can use or implement the following set of heap operations using the heapq module:

  1. heapify(list)
  2. heappush(heap, item)
  3. heappop(heap)
  4. heappushpop(heap, item)
  5. heapreplace(heap, item)
  6. nlargest(item, iterable, key=function)
  7. nsmallest(item, iterable, key=function)

1. heapify

The 'heapify' method is used on a list to perform a heapify operation on it (as the name suggests), which transforms all the elements in the original list that is passed into the function as an argument into a heap (by default, it is a min-heap implementation in Python).

# First importing the heapq Library
import heapq 
# initialising list in python
l = [5, 1, 9, 6, 4, 2, 10]
# performing heapify on list ‘l’
d = 10
# heapified elements of list ‘l’
print( l )
You can also try this code with Online Python Compiler
Run Code

Output:

[1, 4, 2, 6, 5, 9, 10]

Note: The heapify operation modifies all the elements of the list in place and creates a min-heap by default where the minimum element is always at the root
 

2. heappop

The ‘heappop’ method is used to retrieve and remove the minimum element from the heap by maintaining the heap property of the list both before and after the removal.

# First importing the heapq Library
import heapq
l = [1, 4, 2, 6, 5, 9, 10]
# Then printing the value of the popped item from the heap
print (heapq.heappop(l))
You can also try this code with Online Python Compiler
Run Code

Output:

1

 

3. heappush

The 'heappush' takes two parameters viz. Heap to which the given element is to be inserted and the value of the element that it would insert. 

# First importing the heapq Library
import heapq
 
l = [2, 4, 9, 6, 5, 10]
heapq.heappush(l, 3)
print ( l )
You can also try this code with Online Python Compiler
Run Code

Output:

[2, 4, 3, 6, 5, 10, 9]

 

4. heapreplace

This method is a combined implementation of a ‘heappop’ followed by a ‘heappush’

# First importing the heapq Library
import heapq
l = [2, 4, 3, 6, 5, 10, 9]
popped_item = heapq.heapreplace(l, 8)
print(“Popped : “,popped_item)
print(“list after heapreplace: “,l)
You can also try this code with Online Python Compiler
Run Code

Output:

Popped : 2
list after heapreplace: [3, 4, 8, 6, 5, 10, 9]

 

You can compile it with online python compiler.

5. heappushpop

The ‘heappushpop’ method is a combination of a ‘heappush’ followed by a ‘heappop’

# First importing the heapq Library
import heapq
 
l = [3, 4, 8, 6, 5, 10, 9]

popped_item = heapq.heapreplace(l, 4)
print(“Popped : “,popped_item)
print(“list after heappushpop: “,l)
You can also try this code with Online Python Compiler
Run Code

Output:

Popped : 3
list after heappushpop: [4, 4, 8, 6, 5, 10, 9]

 

6. nlargest and nsmallest

These methods in the heapq module are used to retrieve a list of 'N' largest or 'N' smallest elements in a heap. This function takes the iterable as the first parameter, the number of elements to be retrieved as the second and a third optional parameter as a custom comparator function to filter and retrieve such elements internally.


# First importing the heapq Library
import heapq

l = [4, 4, 8, 6, 5, 10, 9]

print(“The 4 smallest items in the heap are :  “,heapq.nsmallest(4, l))
print(“The 4 largest items in the heap are :  “,heapq.nlargest(4, l))
You can also try this code with Online Python Compiler
Run Code

Output

The 4 smallest items in a heap are : [4, 4, 5, 6]
The 4 largest items in a heap are : [10, 9, 8, 6]
You can also try this code with Online Python Compiler
Run Code

 

Must Read Python List Operations

Common Use-cases and applications of Python Heapq

So the most common use-cases and applications for implementing heaps and priority queues using the heapq module are those where there is a requirement to prioritise certain elements from others, such as identifying and selecting the top 'N' or bottom 'N' items from a set of items or when there is a need to merge sorted set of sequences.

Let’s look at very minimal example/simulation for such a use-case and when they might be required to be solved through heaps or some custom implementations of priority queues.

# First importing the heapq module
import heapq
 
# final standings of the Tokyo 2020 Olympics women’s 100m swimming event 
results="""
Cate Campbell                     Australia          52.80
Anna Hopkin                        Great Britain    52.75
Sarah Sjöström                    Sweden           52.91
Siobhan Haughey                Hong Kong      52.70
Penny Oleksiak                   Canada            52.95
Pernille Blume                     Denmark          52.96
Emma McKeon                    Australia          52.13
Yang Junxuan                      China               53.02
"""

standings_list = results.splitlines()

print(standings_list)
# cleaning the data
standings_list.pop(0)
top_three = heapq.nsmallest(3, standings_list, key=lambda x: float(x.split()[-1])) 
print(“\n”.join(top_three))
You can also try this code with Online Python Compiler
Run Code

Output

['', 'Cate Campbell                     Australia          52.80', 'Anna Hopkin                        Great Britain    52.75', 'Sarah Sjöström                    Sweden           52.91', 'Siobhan Haughey                Hong Kong      52.70', 'Penny Oleksiak                   Canada            52.95', 'Pernille Blume                     Denmark          52.96', 'Emma McKeon                    Australia          52.13', 'Yang Junxuan                      China               53.02']

Emma McKeon                    Australia          52.13
Siobhan Haughey                Hong Kong      52.70
Anna Hopkin                        Great Britain    52.75

 

Another such use-case is for which one can leverage the capabilities of a heap for merging sorted sequences of multiple lists of items/iterables. 

# First importing the heapq Library
import heapq
import datetime
# message scheduler utility
def schedule_message(frequency, message_details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, message_details

fast_message = schedule_message(datetime.timedelta(seconds=5), “fast message”)
slow_message = schedule_message(datetime.timedelta(seconds=10), “slow message”)

merged_messages = heapq.merge(fast_message, slow_message)

for _ in range(50):
    print(next(merged_messages))
You can also try this code with Online Python Compiler
Run Code

Output

(datetime.datetime(2022, 2, 20, 22, 11, 52, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 11, 57, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 11, 59, 569174), 'slow message')
(datetime.datetime(2022, 2, 20, 22, 12, 2, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 7, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 12, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 14, 569174), 'slow message')
(datetime.datetime(2022, 2, 20, 22, 12, 17, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 22, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 27, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 29, 569174), 'slow message')
(datetime.datetime(2022, 2, 20, 22, 12, 32, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 37, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 42, 948702), 'fast message')
(datetime.datetime(2022, 2, 20, 22, 12, 44, 569174), 'slow message')
(datetime.datetime(2022, 2, 20, 22, 12, 47, 948702), 'fast message')
…

In this way, one can also merge sorted sequences/lists such as log files by their order of recent creations.

Various other implementations of heap and priority queues for solving problems where one can consider a potential solution using these data structures can be where

  1. It is required to extract out maximum-minimums, largest-smallest, best-worst, etc., from certain data items groups.
  2. Where it is required to find the most efficient, optimum solutions.

 

Also See, Python Round Function and Convert String to List Python.

Finding the Largest and Smallest Elements from a Heap in Python

In Python, the heapq module implements a min-heap, where the smallest element is always at the root. Here's how you can find the smallest and largest elements:

Implementation

import heapq
# Sample heap (min-heap)
heap = [20, 5, 15, 10, 40, 25]
# Convert the list to a heap
heapq.heapify(heap)
# Find the smallest element (root of the heap)
smallest = heap[0]
# Find the largest element
# Since it's a min-heap, the largest element is the max of the list
largest = max(heap)
print("Heap:", heap)
print("Smallest element:", smallest)
print("Largest element:", largest)
You can also try this code with Online Python Compiler
Run Code


Output

Heap: [5, 10, 15, 20, 40, 25]
Smallest element: 5
Largest element: 40

Advantages of Using heapq Module in Python

  • Efficient Insertion and Deletion: heapq provides efficient O(log n) insertion and deletion operations.
     
  • Minimal Memory Overhead: heapq uses a list structure, keeping memory usage low.
     
  • Python Standard Library: Being part of the standard library, no additional installation is needed.
     
  • Easy Min-Heap Implementation: It provides an easy way to maintain a dynamic set of the smallest elements.

Disadvantages of Using heapq Module in Python

  • Min-Heap Only: heapq only supports a min-heap; for a max-heap, you must invert values manually.
     
  • Not Thread-Safe: heapq doesn’t handle concurrency, unlike PriorityQueue which is thread-safe.
     
  • Limited Customization: It lacks built-in support for complex priority functions; custom comparators need extra work.

Frequently Asked Questions

How are max heaps implemented using the heapq Python module?

Since the heapq module by default implements a min-heap, so to use the heap as a max heap, one can either negate all the values that are being inserted in a heap and negate the values back while retrieving them or can custom define an implementation of a comparator function that it can use while building the heap from a given set of values.

Is heapq faster than PriorityQueue?

Yes, heapq is faster than PriorityQueue for most operations because it provides a direct interface for heap operations without the additional overhead of thread-safety features that PriorityQueue includes.

Is heapq part of Python's standard library?

Yes, heapq is part of Python’s standard library. It provides functions to implement a min-heap and offers efficient priority queue functionalities using a list structure.

Does heapq work with strings?

Yes, heapq can work with strings since it treats all elements as comparable objects. It orders them lexicographically, treating smaller strings as having higher priority in the heap.

Conclusion

In this article, we explored the various functionalities of Python's heapq module and its advantages in solving problems like merging sorted values efficiently. We also identified key scenarios where heaps outperform other data structures, offering a reliable solution for optimizing certain operations.

You can also use  Code360 to practice various DSA questions asked in many interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Live masterclass