You’ll learn how to apply heapq in Python modules in this guide. What kinds of problems may a heap be used to solve? How to overcome those problems with Python’s heapq module.
What is a Python Heapq Module?
A heap data structure represents a priority queue. The “heapq” package in Python makes it available. The peculiarity of this in Python is that it always pops the least of the heap pieces (min heap). The heap[0] element always gives the smallest element.
Several heapq routines take a list as an input and organize it in a min-heap order. A flaw with these routines is that they require a list or even a collection of tuples as a parameter. They don’t allow you to compare any other iterables or objects.
Let’s have a look at some of the basic operations that the Python heapq module supports. To acquire a better understanding of how the Python heapq module works, look through the following sections for implemented examples.
Example 1:
The heapq module in Python allows you to perform heap operations on lists. Unlike some of the additional modules, it does not specify any custom classes. The Python heapq module includes routines that operate directly with lists.
Typically, elements are added one by one into a heap, beginning with an empty heap. If there is already a list of elements that have to be converted to a heap, the heapify() function in the Python heapq module can be used to convert the list to a valid heap.
Let’s see the following code step by step. The heapq module is imported in the first line. Following that, we’ve given the list the name ‘one.’ The heapify method has been called, and the list has been provided as a parameter. Finally, the outcome is shown.
one = [7, 3, 8, 1, 3, 0, 2]
heapq.heapify(one)
print(one)
The output of the aforementioned code is shown below.
You can see that, despite the fact that 7 occurs after 8, the list still follows the heap property. For instance, the value of a[2], which is 3, is less than the value of a[2*2 + 2], which is 7.
Heapify(), as you can see, updates the list in place but does not sort it. A heap does not have to be arranged to fulfill the heap property. When heapify() is used on a sorted list, the order of the elements in the list is preserved because every sorted list fits the heap property.
Example 2:
A list of items or a list of tuples can be passed as a parameter to heapq module functions. As a result, there are two options to alter the sorting technique. For comparison, the first step is to transform the iterable into a list of tuples/lists. Make a wrapper class that extends the ” operator. In this example, we’ll look at the first approach mentioned. This method is simple to use and may be applied to comparing dictionaries.
Make an effort to comprehend the following code. As you can see, we’ve imported the heapq module and generated a dictionary called dict_one. Following that, the list is defined for tuple conversion. The function hq.heapify(my list) organizes the lists into a min-heap and prints the result.
Finally, we convert the list to a dictionary and display the results.
dict_one = {'z': 'zinc', 'b': 'bill', 'w': 'wicket', 'a': 'Anna', 'c': 'caouch'}
list_one = [(a, b) for a, b in dict_one.items()]
print("Before organizing:", list_one)
hq.heapify(list_one)
print("After organizing:", list_one)
dict_one = dict(list_one)
print("Final dictionary :", dict_one)
The output is attached below. The final reconverted dictionary is displayed beside the before and after arranged list.
Example 3:
We’re going to incorporate a wrapper class in this example. Consider a scenario in which a class’s objects must be kept in a min-heap. Consider a class that has attributes such as ‘name,’ ‘degree,’ ‘DOB’ (date of birth), and ‘fee.’ This class’s objects must be kept in a min-heap depending on their ‘DOB’ (date of birth).
We now override the relational operator ” in order to compare the fee of each student and return true or false.
Below is the code that you can go through step by step. We’ve imported the heapq module and defined the class ‘student,’ in which we’ve written the constructor and the function for customized printing. As you can see, we’ve overridden the comparison operator.
We’ve now created objects for the class and specified the student’s lists. Based on the DOB, the code hq.heapify(emp) will convert to min-heap. The result is displayed in the final piece of code.
class student:
def __init__(self, a, b, yos, c):
self.name = a
self.degree = b
self.DOB = yos
self.fee = c
def print_me(self):
print("Name :", self.name)
print("Degree :", self.degree)
print("Date of Birth :", str(self.DOB))
print("salary :", str(self.fee))
def __lt__(self, nxt):
return self.DOB < nxt.DOB
std1 = student('Alex', 'Law', 1990, 36000)
std2 = student('Mathew', 'Phd', 1998, 35000)
std3 = student('Tina', 'Computer Science', 1980, 70000)
std4 = student('Jack', 'IT', 1978, 90000)
std = [std1, std2, std3, std4]
hq.heapify(std)
for i in range(0, len(std)):
std[i].print_me()
print()
Here is the complete output of the reference code mentioned above.
Conclusion:
You now have a better understanding of the heap and priority queue data structures and how they might assist you in solving different kinds of problems. You studied how to generate heaps from Python lists using the Python heapq module. You also studied how to utilize the various operations of the Python heapq module. To better comprehend the topic, read the article thoroughly and apply the examples provided.
