The heapq
module is an inbuilt module in Python that offers APIs for different operations of the heap data structure. The module provides min-heap implementation where the key of the parent is less than or equal to those of its children. Some of the functions offered by the module are heapify
and heappushpop
, among others.
Note: To understand more about heaps and priority queues, refer to What is a Heap? and What is the Python priority queue?
heapify()
methodThe heapify()
method converts the given list to a heap in linear time. This operation is in-place, i.e., the method rearranges the elements in the original list without creating a copy of it.
heapify(x)
x
: This refers to the list to be converted to a heap.As the method modifies the list in place, the method doesn’t return anything.
import heapqlst = [28, 2, 32, 22, 10, 1]print("Original list - ", lst)heapq.heapify(lst)print("Heapified list - ", lst)
heapq
module.lst
.lst
to a heap using the heapify
method.In the output, the element at the 0th
index is the smallest element of all elements in the lst
.
Let us explore constructing a heap data structure on custom objects.
Consider the following class called Person
, which has name
and age
as attributes.
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
If we need to construct a heap of Person
objects, then we need to define the __lt__
method. The __lt__
function is the operator overloading function for the less-than operator. This method will contain the logic to compare the age of the Person
objects. We can change the logic in this method depending on the use case.
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def __lt__(self, other):
return self.age < other.age
import heapqclass Person:def __init__(self, name, age):self.name = nameself.age = agedef __repr__(self):return "[" + self.name + ", " + str(self.age) + "]"def __lt__(self, other):return self.age < other.ageperson_lst = [Person("celeste", 34), Person("sam", 23), Person("gaby", 25), Person("john", 15)]print("Original person list - ", person_lst)heapq.heapify(person_lst)print("Heapified perosn list - ", person_lst)
In the above code, we define a list of Person
objects called person_lst
and construct a heap of Person
objects using the heapify()
method.
In the output, the youngest person, john
, is at the 0th
index of all the persons in the person_lst
.