Last Updated on May 12, 2023 by Prepbytes
A heap is simply a binary tree with some additional rules that it has to follow. There are two rules which differentiate heap structures from any other tree structure.
Rules of Heap Data Structure in Python
These rules are: First, a heap must be a complete binary tree. Second, the parent node of a heap must be the ≥ value of its children (max heap) or ≤ value of its children (min-heap)
A complete binary tree’s internal node must have a value larger than or equal to the value of its children for Max-Heap to operate correctly.
The left child of a node put at position k in the array will be maintained at index 2k + 1, and the right child at index 2k + 2.
Representation of Max Heap
The Max heap is represented as an array. The below points show indexes of other nodes for the ith node, i.e. Arr[i]:
- Arr[(i – 1) / 2] returns its parent node.
- Arr[(2 * i) + 1] returns its left child node.
- Arr[(2 * i) + 2] returns its right child node.
For Example 1:
For a node with value 6, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 2. And we can see here that, both the children are bigger than their parent node.
For Example 2: Using the above rules of array representation we can represent a heap in the array:
For a node with value 14, its index value is 2 have left child is at (22) + 1 = 5 i.e. node with value 6 and the right child is at (22) + 2 = 6 i.e. node with value 8. And we can see here that, both the children are smaller than their parent node. Also, its parent node will be at (2-1)/2 = 0 i.e. node with value 18.
Operations on Max Heap in Python
- getMaximum(): The root element of the maximum heap will be returned by this function. Its time complexity is O(1).
- extractMaximum(): The maximum element will be eliminated from the Maxheap using this function. This function, which has a time complexity of 0(Log n), calls the heapify function to retain the heap property after removing the root.
- insertNode(): It takes 0(Log n) time to insert a new key. We shall use this function to add a new key to the binary tree’s end. We need to correct the heap property that is broken in this case if the new key is smaller than its parent.
Note: We have to do indexing to simplify the below implementation.
Code Implementation of Max Heap in Python
import sys
class MaxHeap:
def __init__(self, maxsize):
self.maxsize = maxsize
self.size = 0
self.Heap = [0] * (self.maxsize + 1)
self.Heap[0] = sys.maxsize
self.FRONT = 1
def parent(self, pos):
return pos // 2
def leftChild(self, pos):
return 2 * pos
def rightChild(self, pos):
return (2 * pos) + 1
def isLeaf(self, pos):
if pos >= (self.size//2) and pos <= self.size:
return True
return False
def swap(self, fpos, spos):
self.Heap[fpos], self.Heap[spos] = (self.Heap[spos], self.Heap[fpos])
def maxHeapify(self, pos):
if not self.isLeaf(pos):
if (self.Heap[pos] < self.Heap[self.leftChild(pos)] or
self.Heap[pos] < self.Heap[self.rightChild(pos)]):
if (self.Heap[self.leftChild(pos)] >
self.Heap[self.rightChild(pos)]):
self.swap(pos, self.leftChild(pos))
self.maxHeapify(self.leftChild(pos))
else:
self.swap(pos, self.rightChild(pos))
self.maxHeapify(self.rightChild(pos))
def insertNode(self, element):
if self.size >= self.maxsize:
return
self.size += 1
self.Heap[self.size] = element
current = self.size
while (self.Heap[current] >
self.Heap[self.parent(current)]):
self.swap(current, self.parent(current))
current = self.parent(current)
def Print(self):
for i in range(1, (self.size // 2) + 1):
print("PARENT NODE : " + str(self.Heap[i]) +
" LEFT CHILD : " + str(self.Heap[2 * i]) +
" RIGHT CHILD : " + str(self.Heap[2 * i + 1]))
def extractMaximum(self):
popped = self.Heap[self.FRONT]
self.Heap[self.FRONT] = self.Heap[self.size]
self.size -= 1
self.maxHeapify(self.FRONT)
return popped
if __name__ == "__main__":
maxHeap = MaxHeap(15)
maxHeap.insertNode(5)
maxHeap.insertNode(9)
maxHeap.insertNode(1)
maxHeap.insertNode(11)
maxHeap.insertNode(28)
maxHeap.insertNode(19)
maxHeap.insertNode(7)
maxHeap.insertNode(2)
maxHeap.insertNode(8)
maxHeap.Print()
print("The Max val is of Max Heap will be " + str(maxHeap.extractMaximum()))
Output:
PARENT NODE : 28 LEFT CHILD : 11 RIGHT CHILD : 19
PARENT NODE : 11 LEFT CHILD : 8 RIGHT CHILD : 9
PARENT NODE : 19 LEFT CHILD : 1 RIGHT CHILD : 7
PARENT NODE : 8 LEFT CHILD : 2 RIGHT CHILD : 5
The Max val is of Max Heap will be 28Implementation using Library Functions
When you want to remove the elements with the highest or lowest order/priority, you use the heap. These elements can be accessed quickly in O(1) time thanks to the heap. However, since the heap is not ordered (we must cycle through all the nodes), locating other elements takes O(n) time. The heap only allows quick access to the lowest or greatest elements.
You may generate a min heap or max heap in Python using the heapq package. By default, a heap created with the heapq function is always a min heap, which means that each time, the smallest element is removed from the heap.
A few useful functions are available in the heapq module to carry out various operations on the heap data structure. Here are these functions:
- heapify: In-place and in linear time, this function transforms an iterable into a heap data structure. The heap’s elements will be rearranged after calling this function such that it has the property of a min heap.
- heappush: This function adds an element to a heap and, after insertion, modifies the order to preserve the heap’s structure. This action is completed in O(log(n)) time by the help push function, where n is the size of the heap.
- heappop: The smallest element in a heap is removed by this function, and it is then returned. The order is then altered appropriately to preserve the heap’s structure. This process is completed by the heappop function in O(log(n)) time, where n is the heap’s size.
- heappushpop: Elements can be pushed and removed from the heap using this function. The specified element* is first pushed to the heap by this function, after which the smallest element is pulled off the heap. This operation is completed in O(log(n)) time by the heappushpop function, where n is the size of the heap.
- heapreplace: Additionally, this function pops and pushes elements in a heap. But instead, it "pushes the provided element back into the heap" after "popping the smallest element* from the heap." This procedure is completed by the heapreplace function in O(log(n)) time, where n is the heap’s size.
- nlargest: The k biggest elements from the heap are returned by this function. The size parameter supplied to the function, k, determines how long it takes to complete a task in O(log(k)) time.
- nsmallest: From the heap, this function returns the k-smallest elements. The size parameter supplied to the function, k, determines how long it takes to complete a task in O(log(k)) time.
Let’s see the code implementation of a few functions from the heapq module in Python.
Code Implementation
import sys
class MaxHeap:
def __init__(self, maxsize):
self.maxsize = maxsize
self.size = 0
self.Heap = [0] * (self.maxsize + 1)
self.Heap[0] = sys.maxsize
self.FRONT = 1
def parent(self, pos):
return pos // 2
def leftChild(self, pos):
return 2 * pos
def rightChild(self, pos):
return (2 * pos) + 1
def isLeaf(self, pos):
if pos >= (self.size//2) and pos <= self.size:
return True
return False
def swap(self, fpos, spos):
self.Heap[fpos], self.Heap[spos] = (self.Heap[spos], self.Heap[fpos])
def maxHeapify(self, pos):
if not self.isLeaf(pos):
if (self.Heap[pos] < self.Heap[self.leftChild(pos)] or
self.Heap[pos] < self.Heap[self.rightChild(pos)]):
if (self.Heap[self.leftChild(pos)] >
self.Heap[self.rightChild(pos)]):
self.swap(pos, self.leftChild(pos))
self.maxHeapify(self.leftChild(pos))
else:
self.swap(pos, self.rightChild(pos))
self.maxHeapify(self.rightChild(pos))
def insertNode(self, element):
if self.size >= self.maxsize:
return
self.size += 1
self.Heap[self.size] = element
current = self.size
while (self.Heap[current] >
self.Heap[self.parent(current)]):
self.swap(current, self.parent(current))
current = self.parent(current)
def Print(self):
for i in range(1, (self.size // 2) + 1):
print("PARENT NODE : " + str(self.Heap[i]) +
" LEFT CHILD : " + str(self.Heap[2 * i]) +
" RIGHT CHILD : " + str(self.Heap[2 * i + 1]))
def extractMaximum(self):
popped = self.Heap[self.FRONT]
self.Heap[self.FRONT] = self.Heap[self.size]
self.size -= 1
self.maxHeapify(self.FRONT)
return popped
if __name__ == "__main__":
maxHeap = MaxHeap(15)
maxHeap.insertNode(5)
maxHeap.insertNode(9)
maxHeap.insertNode(1)
maxHeap.insertNode(11)
maxHeap.insertNode(28)
maxHeap.insertNode(19)
maxHeap.insertNode(7)
maxHeap.insertNode(2)
maxHeap.insertNode(8)
maxHeap.Print()
print("The Max val is of Max Heap will be " + str(maxHeap.extractMaximum()))
Output:
The Head value of heap is : 28
Heap elements are :
28 11 19 8 9 1 7 2 5
The heap elements :
19 11 7 8 9 1 5 2Conclusion
We had discussed multiple approaches for the implementation of the max heap in Python. Besides this, there is more logic for the max heap implementation in Python. Practice more to figure out that. Also, in this article, a brief about a few functions of the heap module in Python is given, implement all those function to grab more about Python and heap.
FAQ related to Max Heap in Python
Q1. Where is the max heap used?
Ans. There are two types of heaps: Min-heap and Max-heap. A min-heap is used to access the minimum element in the heap whereas the Max-heap is used when accessing the maximum element in the heap.
Q2. Why use heap in Python?
Ans. The heap is used when you want to remove the highest or lowest order/priority elements and it allows quick access to these elements in O(1) time.
Q3. Is a heap a tree?
Ans. A heap is a tree-based data structure in which all the nodes of the tree are in a specific order.