What is the heapq.heapify() module in Python?

Overview

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?

The heapify() method

The 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.

Syntax

heapify(x)

• x: This refers to the list to be converted to a heap.

Return value

As the method modifies the list in place, the method doesn’t return anything.

Code

Explanation

• Line 1: We import the heapq module.
• Line 3: We define a list of integers called lst.
• Line 7: We convert the 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.

Using custom objects

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

Explanation

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.