Max Heap in Python

Heapq module in Python

The heapq is a built-in Python library that has been available since Python 2.3. It implements a min heap, and its functions are designed to work with lists.

The below given example is of how to use the heapq module to implement a max heap using min-heap in Python:

• Python

Python

import heapq

heap = []
# add elements to heap
heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -10)

# get the maximum element
print(-heapq.heappop(heap))

You can also try this code with Online Python Compiler

Run Code

Output:

10

In python 3.9 and above, there is a built-in heap module that you can use to create a max heap.

You can also read about the Multilevel Inheritance in Python, Swapcase in Python

Representation of Max Heap in Python

A max heap is typically represented using an array or a list in computer memory. The root node of the heap is stored at the first position of the array (index 0), and the remaining nodes are stored in breadth-first order.

In Breadth-First Search, we traverse level by level means it visits all the vertices at the current depth level before moving on to the next level.

The node's left and right children at index i are stored at indices 2i+1 and 2i+2 (for 0-indexed arrays). The node's parent at index i is stored at index (i-1)//2.

For example, the following binary tree:

The following array can be used to represent the above binary tree as a max heap:-

[10, 5, 15, 3, 7, 12]

A max heap in Python is complete, meaning all levels of the tree are filled, except possibly the last level, and the previous level is filled from left to right. You can also use Python's heapq.heapify() function converts a given list of items into a heap.

The below example converts the list into a max heap.

• Python

Python

import heapq

li = [10, 5, 15, 3, 7, 12]
heapq.heapify(li)
print(li)

You can also try this code with Online Python Compiler

Run Code

Output

[3, 5, 12, 10, 7, 15]

Must Read Python List Operations

Operation on Max Heap in Python

Several operations can be performed on a max heap in Python:

1. heapq.heappush(heap, item): This function pushes the item onto the heap, maintaining the heap property.

2. heapq.heappop(heap): This function removes and returns the largest item from the heap. If the heap is empty, an index error is raised.

3. heapq.heappushpop(heap, item): This function combines the functionality of both push and pop operations in one statement, increasing efficiency. It pushes the item on the heap and then pops the largest item.

4. heapq.heapreplace(heap, item): This function also combines the functionality of both push and pop operations in one statement. It pops the largest item and then pushes the new item.

5. heapq.heappop(heap): This function keeps the heap property while removing and returning the smallest item from the heap.

6. heapq.heapify(iterable): This function transforms the iterable into a heap, in place, in linear time.

Example

An example to understand the above operation on the max heap in Python is:

• Python

Python

import heapq


# create a max heap
heap = [-5, -1, -10]
heapq.heapify(heap)

# get the maximum element
print(-heapq.heappop(heap)) 


# push an element
heapq.heappush(heap, -7)
heapq.heapreplace(heap, 2)

# get the maximum element
print(-heapq.heappop(heap))
print(-heapq.heappushpop(heap, 4))

You can also try this code with Online Python Compiler

Run Code

Output

10
5
1

Check out this article - String slicing in Python, and Convert String to List Python

Check out Escape Sequence in Python

Max Heap Implementation in Python

In Python, a Max Heap implementation typically involves defining a class that encapsulates the necessary methods for heap operations. Let's implement a Max Heap in Python for each of the specified conditions:

Using Library functions

• Python

Python

from heapq import heappop, heappush, heapify

# Creating an empty max heap
max_heap = []
heapify(max_heap)

# Adding values to max heap
heappush(max_heap, -15)
heappush(max_heap, -20)
heappush(max_heap, -87)
heappush(max_heap, -304)

# Printing the value of the maximum element
print("Maximum value in the max heap: " + str(-max_heap[0]))

# Printing the elements of the max heap
print("The max heap elements: ")
for item in max_heap:
    print(-item, end=" ")
print("\n")

# Extracting the maximum element from the max heap
max_element = heappop(max_heap)

# Printing the elements of the max heap after extraction
print("The max heap elements after extracting maximum: ")
for item in max_heap:
    print(-item, end=' ')

You can also try this code with Online Python Compiler

Run Code

Output:

Maximum value in the max heap: 304
The max heap elements: 
304 87 20 15 

The max heap elements after extracting maximum: 

87 15 20

Using Library Functions with Special Methods for Numbers, Strings, Tuples, Objects, etc

• Python

Python

from functools import total_ordering
import heapq

# Define a class with total ordering
@total_ordering
class Wrapper:
    def __init__(self, val):
        self.val = val

    # Define less than comparison
    def __lt__(self, other):
        return self.val > other.val

    # Define equality comparison
    def __eq__(self, other):
        return self.val == other.val

# Working on an existing list of integers
int_heap = [5, 40, 390, 85]
wrapper_int_heap = [Wrapper(item) for item in int_heap]

# Convert list of integers to a max heap
heapq.heapify(wrapper_int_heap)

# Extract the maximum item from the max heap
max_item_int = heapq.heappop(wrapper_int_heap)

# Print the maximum value
print(f"Maximum value in the integer heap: {max_item_int.val}")

# Working on an existing list of strings
str_heap = ["are", "best", "the", "ninjas"]
wrapper_str_heap = [Wrapper(item) for item in str_heap]

# Convert list of strings to a max heap
heapq.heapify(wrapper_str_heap)

# Extract elements from the max heap and print them
print("The string heap elements in order: ")
while wrapper_str_heap:
    top_item_str = heapq.heappop(wrapper_str_heap)
    print(top_item_str.val, end=" ")

You can also try this code with Online Python Compiler

Run Code

Output:

Maximum value in the integer heap: 390
The string heap elements in order: 
the ninjas best are

Using Functions in heapq Library

• Python

Python

from heapq import _heapify_max, _heappop_max, _siftdown_max

def heappush_max(max_heap, item): 
    max_heap.append(item)
    _siftdown_max(max_heap, 0, len(max_heap)-1)

def max_heap(og_arr):
    copy = og_arr.copy() 
    _heapify_max(og_arr)  
    while len(og_arr) != 0:  
        print(_heappop_max(og_arr))  
    og_arr = copy  
    max_heap = []
    
    for item in og_arr:
        heappush_max(max_heap, item)
    print("This is max heap!")
    while len(max_heap) != 0:  
        print(_heappop_max(max_heap))  
og_arr = [16, 38, 45, 22, 11, 15]
max_heap(og_arr)

You can also try this code with Online Python Compiler

Run Code

Output:

45
38
22
16
15
11
This is max heap!
45
38
22
16
15
11

Frequently Asked Questions

What is min heap and max heap Python library?

Python's heapq module provides functions for implementing min heaps and max heaps using a list-based binary heap.

What is the function of Maxheap?

The function of MaxHeap is to maintain a binary heap where the parent node is greater than or equal to its children.

What is the default heap in Python?

The default heap in Python is a min-heap, where the smallest element is the root.

What is the max-heap rule?

The max-heap rule states that in a binary max-heap, the parent node must be greater than or equal to its children.

What is heap data structure?

A heap is a specialized type of tree-based data structure that satisfies the following requirement: if P is a parent node of C, then P's key must be either greater than or equivalent to (in a max heap) or less than or equal to (in a min-heap) the key of C.

Explain some real-time applications of the heap.

Heaps are commonly used in various real-life applications, such as Operating Systems, Priority queues, Graphs Algorithm, Sorting Algorithms, Databases, Network routing, data compression, Artificial Intelligence, etc.

Conclusion

This blog discussed the Max Heap in Python. Max Heap in Python is a functional data structure in computer science that can be implemented in Python using the built-in heapq module or the heap module.

To see and learn more about graphs related to the max heap in Python, please read the following articles:

Recommended Readings:

• Distance Vector Routing Algorithm
• Fibonacci Series in Python
• Python String Concatenation
• Implementation of Heap
   

You can also consider our paid courses such as DSA in Python to give your career an edge over others!

We wish you Good Luck! 

Happy Learning!