In this article, we will learn more about Max Heap (known as heap queue in Python). We have already learned about Heap and its library functions (in heapq module) in python . We will now learn about max heap and its implementation and then look at the Python code for implementing the heapify, heappush and heappop functions for max-heap ourselves.
What is a Max heap?
Max Heap is a complete binary tree (Complete binary tree is a tree that is completely filled, except for the rightmost nodes in the deepest/last level ) in which each node is greater than or equal to all its children. Hence the root node of a heap is the largest element. The heap data structure is generally used to represent a priority queue, and max heap can be understood as a priority queue with the maximum element as the highest priority.
How is max-heap represented in an array?
We have already seen how a heap is represented in memory in the form of an array, just a quick reminder that:
- The root element will be at the zeroth position of the array, that is, Heap[0].
- For any other node, say Heap[i], we have the following:
- The parent node is given by : Heap[(i -1) / 2]
- The left child node is given by : Heap[(2 * i) + 1]
- The right child node is given by : Heap[(2 * i) + 2]
A heap in Python is by default Min-heap, and is used using the heapq module’s heapify, heappop, and heappush functions.
To create and use a max-heap using library functions, we can multiply each element with -1 and then use the heap library function, and hence it will act as a max-heap.
Let us now understand how max-heap functions work and how we can write code to implement these functions from scratch.
Understanding the functions for implementing max heap
1. max-heapify function
This function makes a node and all its descendants (child nodes and their child) follow the max heap property. It rearranges the nodes by swapping them so as to make the given heap the largest node in its subtree, following the max-heap property.
It first finds the node with the largest value amongst the given node and all its children. It then swaps the given node, (say i) with the found maximum value node (say j), and then calls the max-heapify function (recursively) over node j, so as to make sure the new value assigned to node j does not break the max-heap property in its subtree.
Since at most, it has to traverse through the depth of the tree, its time complexity is O(d), d is the depth, or, in terms of the number of nodes, O(log n), n is the number of elements in the heap.
2. build-heap function
This function builds a heap from an arbitrary list (or any other iterable), that is, it takes the list and rearranges each element so as to satisfy the max-heap property.
It can simply be implemented by applying max-heapify to each node repeatedly. The time complexity of this function comes out to be O(n).
3. heappop function
This function pops out the maximum value (root element) of the heap.
This is actually done by swapping the root node with the last node and deleting the now last node (containing maximum value now) and then calling max-heapify for the root node so as to maintain the heap property after changes due to swapping.
Since we only need to deal with the descendants, the time complexity is O(log n), where n is the number of elements, or O(h), where h is the height of the tree which is log n as it is a complete tree.
4. heappush function
This function pushes a new element into the heap, and arranges it into its correct position, maintaining the heap property.
This is actually done by adding a new node to the end of the heap. Now to maintain the heap property, we traverse up from the last node (and swap where needed) to fix the heap property which might be violated due to addition of the pushed element.
In a similar way as heappop, the time complexity here is O(log n) as we only need to traverse the height of the subtree.
5. extractMax function
This function returns the most priority (the root element or largest element) from the heap. Since we just need to return the value of the root and do no change to the heap, and the root is accessible in O(1) time, hence the time complexity of the function is O(1).
Complete Python Implementation of Max Heap
Now, we will implement a max-heap in Python. We use a list [15, 7, 9, 4, 13] in the code and convert it to a max heap using the build-heap function. The heap made would look like this:
Implementation:
import sys
#defining a class max_heap for the heap data structure
class max_heap:
def __init__(self, sizelimit):
self.sizelimit = sizelimit
self.cur_size = 0
self.Heap = [0]*(self.sizelimit + 1)
self.Heap[0] = sys.maxsize
self.root = 1
# helper function to swap the two given nodes of the heap
# this function will be needed for max-heapify and insertion
# in order to swap nodes which are not in order (not satisfy max-heap property)
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
# THE MAX_HEAPIFY FUNCTION
def max_heapify(self, i):
# If the node is a not a leaf node and is lesser than any of its child
if not (i >= (self.cur_size//2) and i <= self.cur_size):
if (self.Heap[i] < self.Heap[2 * i] or self.Heap[i] < self.Heap[(2 * i) + 1]):
if self.Heap[2 * i] > self.Heap[(2 * i) + 1]:
# Swap the node with the left child and call the max_heapify function on it
self.swapnodes(i, 2 * i)
self.max_heapify(2 * i)
else:
# Swap the node with right child and then call the max_heapify function on it
self.swapnodes(i, (2 * i) + 1)
self.max_heapify((2 * i) + 1)
# THE HEAPPUSH FUNCTION
def heappush(self, element):
if self.cur_size >= self.sizelimit :
return
self.cur_size+= 1
self.Heap[self.cur_size] = element
current = self.cur_size
while self.Heap[current] > self.Heap[current//2]:
self.swapnodes(current, current//2)
current = current//2
# THE HEAPPOP FUNCTION
def heappop(self):
last = self.Heap[self.root]
self.Heap[self.root] = self.Heap[self.cur_size]
self.cur_size -= 1
self.max_heapify(self.root)
return last
# THE BUILD_HEAP FUNCTION
def build_heap(self):
for i in range(self.cur_size//2, 0, -1):
self.max_heapify(i)
# helper function to print the heap
def print_heap(self):
for i in range(1, (self.cur_size//2)+1):
print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) + " Right Child is "+ str(self.Heap[2 * i + 1]))
maxHeap = max_heap(10)
maxHeap.heappush(15)
maxHeap.heappush(7)
maxHeap.heappush(9)
maxHeap.heappush(4)
maxHeap.heappush(13)
maxHeap.print_heap()
Output:
Parent Node is 15 Left Child is 13 Right Child is 9
Parent Node is 13 Left Child is 4 Right Child is 7
The output can be verified from the illustration given in the example image.
Conclusion
In this article, We learned about the max-heap. We studied how the functions for max-heapify, heappush, heappop and build_heap work. We further implemented these functions in python from scratch. Stay tuned for more informative articles.
Happy Learning!