Python Heapq: Boost Your Efficiency with Heap Operations!

The heapq module is a module for Python that implements heaps with priority queues. This post will show you how to use the heapq module, including how to create your own heaps and implement them with priority queues.

Priority queues are one of the data structures for stacks and queues. Heapq helps to execute such queues. In other words, the module suits situations where you need a stable and efficient implementation of priority queues.

Priority Queue

The PriorityQueue, or heapq module in Python, is a data structure for dynamic priority queues with O(1) lookup time. It generalizes the singly linked list to allow for multiple elements with different access times. This data structure can be used to implement priority queue algorithms and maintainers.

A priority queue is an ordered list where each element has a value and must be smaller than or equal to the element before it and greater than or equal to the element after it.

What is heapq in Python?

Heapq, the heap module in Python, offers a lot of functionality for building data structures. It is similar to the Queue module in that it allows you to build data structures on top of itself and add elements one by one. Heapq also has some additional functionality that Queue does not have, like the ability to iterate over items in the Queue and support multi-level queues.

Heapq was in Python 3.3 version. It is in all versions after 3.3.

The most common use case for heapq is to build a priority queue (also known as a deque).

Functions of heapq module

heapq have multiple functions like heapify, heapreplace, heappop, heappush, etc.

Heapify

It helps to create a heap out of a list. It will arrange and put the smallest member of the list in the first position. Let’s look at the following example to get a better understanding :

import heapq
H = [2,1,4,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Hence, the output will be:

[1, 2, 4, 3, 5]
#So,heapify brought the smallest number,1 to the beginning 

Heapreplace

It replaces the smallest element with the number you have entered as an argument. There is no particular order/ place where the element will be inserted.

import heapq
H1 = [2,1,4,3,5]
heapq.heapify(H1)
heapq.heapreplace(H1,2)
print(H1)
#Output :
#[2, 2, 4, 3, 5]

Heappop

It is used to pop the first unwanted element from the list.

import heapq
H1 = [2,1,4,3,5]
heapq.heappop(H1)
print(H1)

The output will be:

[1, 3, 4, 5]

You can also use heapify function followed by heappop to pop the smallest element at the first index. Look at this example :

import heapq
H1 = [2,1,4,3,5]
heapq.heapify(H1)
heapq.heappop(H1)
print(H1)
#output: [2, 3, 4, 5]

Heappush

As the name suggests, it helps to push a new number into the heap or add a new number to the list.

import heapq
HEAP = [2,1,4,3,5]
heapq.heappush(HEAP,10)
print(HEAP)
#OUTPUT: [2, 1, 4, 3, 5, 10]

Trending

[Fixed] typeerror can’t compare datetime.datetime to datetime.date

heapq python comparator

Only lists and tuples work with heapq. There might be a case when you have to work with some other data type, like a dictionary. So, in this case, we will convert the dictionary to a tuple.

import heapq as hq 
Newdict= {'z': 'Daman and Diu', 'b': 'Chandigarh', 'a': 'Punjab', 'm': 'Sikkim', 'c': 'Goa'} 

#change dictionary to list
Newlist = [(k, v) for k, v in my_dict.items()] 
print("List format :", Newlist) 
#Make a heap from the list
hq.heapify(Newlist) 
print("Heap format with list:", Newlist) 
# Output the answer as dictionary(original)
Newdict = dict(Newlist) 

heapq ‘not supported between instances’

We know that a heapq works with lists and tuples. This issue arises when the <= operator used by heapq can’t make a comparison between the tuple or lost components.

There might arise a situation when the tuple components of the tuples that have to be compared are NOT DIFFERENT. In this situation, we will get an error. For example:

A = (5, object())
B= (2, object())
C= (5, object())
print(A<= B) #FALSE
print(A<= C) #error

The operator compares the first two components usually. To get over this issue, we can use a comparison operator directly, like __lt__(self, other) for < or __le__(self, other) for <= and others.

Built-in heapq

The heapq module is a built-in module in Python. This means that the functionalities of heapq are predefined.

Check for a node in heapq

Use any to find if an element is present in a heap. The following example will suffice-

myheap = []
X= (321,4)
Y = (258,3)
heapq.heappush(myheap,X)
heapq.heappush(myheap,Y)
node = 4
if any(node in i for i in myheap):
       print('Found')

#we used the heappush function whose use is stated above

Change priority in heapq

You can easily change the priority of the element in heapq. Update it the way you do with lists because originally, heapq is formed of lists and tuples only. This piece of code will make it easy to interpret updating priority in heapq.

import heapq
myheap = []
heapq.heappush(myheap, (2, "Books"))
heapq.heappush(myheap, (4, "Laptop"))
heapq.heappush(myheap, (5, "Pencils"))
print(myheap)
myheap[0] = (3, 'Pencils')
print(myheap)
heapq.heapify(myheap)
print(myheap)

Push the Priority key and value pair into the heap. Now, if you want to change the priority of an element, you can just use the index and update it. Simply equate the new priority and use heapify() function to store this in heap format. Let’s look at the output.

[(2, 'Books'), (4, 'Laptop'), (5, 'Pencils')]
[(3, 'Pencils'), (4, 'Laptop'), (5, 'Pencils')]
[(3, 'Pencils'), (4, 'Laptop'), (5, 'Pencils')]

Sorted heapq

Use the sorted function to sort the heap. If you want it in reverse order, you can use the reverse argument as True.

import heapq
Aheap = []
heapq.heappush(Aheap, (5, "A"))
heapq.heappush(Aheap, (1, "B"))
heapq.heappush(Aheap, (9, "C"))
heapq.heappush(Aheap, (4, "D"))
print(sorted(Aheap, reverse=True))
#for reverse order

Hence, the output is:

[(9, 'C'), (5, 'A'), (4, 'D'), (1, 'B')]

Heapq time complexity

The complexity of the heapify function is O(logn).

python heapq custom comparator

Python has a heapq module that allows you to work with sorted collections of objects. The heapq module has a custom comparator, which is useful for sorting data in Python. This is convenient if you want to implement your own custom data structure but still want to be able to use Heapq for efficient in-memory operations. So, it is a custom comparator that does not use the default heapq.bucket_by_key function, but instead uses a custom one. Here is an example:

from heapq import Heapq
my_cmp = lambda x, y: (x > y) != None 
print(Heapq([1, 2, 3], my_cmp))
# [True, True, False]

When comparing two values in heapq, it will compare them using the < operator. This means that when you use my_cmp as a comparator for the elements of a list object, it will look at the first element of the list object and compare it to the second element. If they are equal, then they are considered equal. If they are unequal, then they are not considered equal.

So let’s say that we want to check whether an integer is greater than its square root. In this case, we need to write another function that does what my_cmp does but for integers instead of strings!

Python heapq Vs Priority queue

Heapq and priority queue are two of the most common collections in Python. They are both used for sorting and searching, but they are different. Let’s look at the differences offered by heapq and priority queue.

python heapq tuple

Python has a built-in module called heapq that you can use to create tuples. A tuple is a data structure that consists of two or more values stored in memory at once, ordered in a particular way. Python’s heapq is a higher-level way of handling tuples. Heapq is a way to organize and work with Python dictionaries and lists into tuples. It is similar to the way you might organize your data in a spreadsheet, where you have cells that are rows and columns.

The syntax for creating a tuple is as follows:

(value1, value2, ..., valueN)

The above example shows how to create an empty tuple using three elements: value1, value2, and valueN. If we want to add more values to the tuple, we can add more elements after the opening parenthesis and separate them with commas. For example:

(1,"Hello", 2)

A heapq object allows you to convert any Python object into an ordered set of values in such a way that each value can be accessed using its key. Heapq objects allow for efficient access using hashing functions. Each key looks up its value by name. means that no lookup operations are required for accessing elements with equal keys (though some may still be required for equal keys not present within the set). Heapq objects are constructed from dictionaries or lists by calling the function get_heapq()

FAQs

Conclusion

In this tutorial, we discussed the Python heapq module in detail. By now, you must have got a fair idea of how the module works, its functions, and the usage of the priority queue in Python.