Definition
The heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.
The above image represents a min-heap
The tree structure in the diagram is an imaginary structure and this structure is going to be implemented completely in an array, the important point is how we are going to link the elements in an array so that we could logically form a tree and the structure as a whole is more efficient than a normal array.
A basic heap with a parent, one left child and one right child
Visualising The Working Of Heap Sort Using Min Heap
Let's take an array of size 5 and build a min-heap out of it and finally, remove the least element one by one(sort by ascending order). In the process, you'll understand how a min-heap is formed and how sorting by ascending order is done using the heap sort algorithm.
1. Insert 5 elements one by one
In the above image you could observe that as soon as soon as 5(i.e 0005) was inserted it shifted upwards and 7(i.e 0007) now became the left child to 5, this process of shifting is done to maintain the min-heap property
Now as soon as 6(i.e 0006) was inserted as it is greater than 5(i.e 0005) so 5 was not replaced instead 6 was added as the right child to 5.
According to min-heap property the smallest element in the array will always remain on the top.
Now when we try to insert 4(i.e 0004) it replaced the root node 5 as 4 is smaller than 5 and 5 replaced 7 as 5 is smaller than 7. One important thing to note here is that not only the root node tries to maintain the min-heap property, but any swap that happens at any level of the heap follows the min-heap property like the swap that we observed above.
Finally, the last element 8(i.e 0008) is inserted and it takes gets added as the right child to 5.
2. Delete/Remove element from heap
Now let's try to delete or remove the root node from the heap(this operation is nothing but getting the smallest element in the heap)
We could observe that 5(i.e 0005) takes up the new root node position 7 moves up and 8 becomes the left child of 7.
What we imagined and what actually happened...
We performed all the min-heap building operations and operations that helped to maintain the min-heap property, but we imagined that everything happened on the heap(tree-like structure in the above diagrams) but all these operations happen on an array. There are 3 formulae that link an array and the imaginary heap structure in our heads.
Parent index = (index - 1)//2
Left Child index = 2*index+1
Right Child index = 2*index+2
(NOTE - Indexing in python starts from 0 so index of the element 10 in array is 0)
In the above figure lets consider elements 23, 32, 38 and their corresponding indexes are 1, 3, 4, now
Parent(element 38) i.e Parent(index 4) is
(index-1)//2 i.e (4-1)//2 = 1
The element in index 1 is 23
LeftChild(element 23) i.e LeftChild(index 1) is
2*index+1 i.e (2*1)+1 = 3
The element in index 3 is 32
RightChild(element 23) i.e RightChild(index 1) is
2*index+2 i.e (2*1)+2 = 4
The element in index 4 is 38
Building A Min-Heap Using Python
The first step is to build a min heap using the elements of an array.
Let's take an unsorted array with 5 elements
unsorted_array = [2,10,9,12,11]
We are going to code the whole min-heap data structure as a single class (The code snippets below may not follow proper indentation, the whole code is attached as a single block at the end).
class MinHeap:
def __init__(self, capacity) -> None:
self.storage = [0]*capacity
self.capacity = capacity
self.size = 0
storage - Array equivalent to the size of the heap
capacity - Size of unsorted array/heap
size - This variable is used for building the array
Helper Functions
We will have a few helper functions which would help in building the heap and sorting the elements in it.
def getParentIndex(self, index):
return (index - 1)//2
def getLeftChildIndex(self, index):
return 2*index+1
def getRightChildIndex(self, index):
return 2*index+2
The above three functions are used to get the parent index, left child index and right child index.
def hasParent(self, index):
return self.getParentIndex(index) >= 0
def hasRightChild(self, index):
return self.getRightChildIndex(index) < self.size
def hasLeftChild(self, index):
return self.getLeftChildIndex(index) < self.size
This above functions are used to check whether a node has a parent node or not, has right child or not, has left child or not.
def parent(self, index):
return self.storage[self.getParentIndex(index)]
def leftChild(self, index):
return self.storage[self.getLeftChildIndex(index)]
def rightChild(self, index):
return self.storage[self.getRightChildIndex(index)]
The above functions are used to get the parent element, left child element and right child element.
def isFull(self):
return self.size == self.capacity
The above function is used to check if the heap is full or not.
def swap(self, index1, index2):
temp = self.storage[index1]
self.storage[index1] = self.storage[index2]
self.storage[index2] = temp
The above function is used to swap two elements in the heap(array).
Now comes 4 important functions that help to build the heap, to maintain the min-heap property and get elements in ascending order from the heap.
def heapifyUp(self, index):
if self.hasParent(index) and (self.parent(index) > self.storage[index]):
self.swap(self.getParentIndex(index), index)
self.heapifyUp(self.getParentIndex(index))
heapifyUp function is used while building the min-heap. When we try to insert an element into the array(heap), this function checks if that index has a parent index(parent node) and whether the parent is smaller or not, if not then a swap happens, and a recursive call is made with the parent index. These operations are done to build the min-heap and maintain the min-heap property.
def insert(self, data):
if self.isFull():
raise("Heap Is Full")
self.storage[self.size] = data
self.size += 1
self.heapifyUp(self.size - 1)
insert function is used along with heapifyUp to build the heap. It checks if the heap is already full, and raises an error if full, if not adds elements to storage which is the heap array.
def heapifyDown(self, index):
smallest = index
if self.hasLeftChild(index) and self.storage[smallest] > self.leftChild(index):
smallest = self.getLeftChildIndex(index)
if self.hasRightChild(index) and self.storage[smallest] > self.rightChild(index):
smallest = self.getRightChildIndex(index)
if smallest != index:
self.swap(index, smallest)
self.heapifyDown(smallest)
heapifyDown is used while removing elements from the heap, it is used to main the heap property by finding the smallest element in the heap and placing it at the root of the heap. Let's take a scenario where the left child to the root node is smaller than the root node, now smallest is assigned with the left child index but the right child is even smaller than the left child, so now smallest will be assigned with the right child index and a swap will happen between root and right child, now a recursive call will happen until the smallest element in heap is the new root node.
def removeMin(self):
if self.size == 0:
raise("Heap is empty")
data = self.storage[0]
self.storage[0] = self.storage[self.size - 1]
self.size -= 1
self.heapifyDown(0)
return data
removeMin is used along with heapifyDown to remove the smallest element(root node from the heap). It removes the smallest element and then assigns the last element as the new root node, reduces the size of the heap array by 1, calls the heapifyDown to restore the min-heap property and returns the removed element.
Complete Implementation Of Min-Heap
class MinHeap:
def __init__(self, capacity) -> None:
self.storage = [0]*capacity
self.capacity = capacity
self.size = 0
def getParentIndex(self, index):
return (index - 1)//2
def getLeftChildIndex(self, index):
return 2*index+1
def getRightChildIndex(self, index):
return 2*index+2
def hasParent(self, index):
return self.getParentIndex(index) >= 0
def hasLeftChild(self, index):
return self.getLeftChildIndex(index) < self.size
def hasRightChild(self, index):
return self.getRightChildIndex(index) < self.size
def parent(self, index):
return self.storage[self.getParentIndex(index)]
def leftChild(self, index):
return self.storage[self.getLeftChildIndex(index)]
def rightChild(self, index):
return self.storage[self.getRightChildIndex(index)]
def isFull(self):
return self.size == self.capacity
def swap(self, index1, index2):
temp = self.storage[index1]
self.storage[index1] = self.storage[index2]
self.storage[index2] = temp
def heapifyUp(self, index):
if self.hasParent(index) and (self.parent(index) > self.storage[index]):
self.swap(self.getParentIndex(index), index)
self.heapifyUp(self.getParentIndex(index))
def insert(self, data):
if self.isFull():
raise("Heap Is Full")
self.storage[self.size] = data
self.size += 1
self.heapifyUp(self.size - 1)
def heapifyDown(self, index):
smallest = index
if self.hasLeftChild(index) and self.storage[smallest] > self.leftChild(index):
smallest = self.getLeftChildIndex(index)
if self.hasRightChild(index) and self.storage[smallest] > self.rightChild(index):
smallest = self.getRightChildIndex(index)
if smallest != index:
self.swap(index, smallest)
self.heapifyDown(smallest)
def removeMin(self):
if self.size == 0:
raise("Heap is empty")
data = self.storage[0]
self.storage[0] = self.storage[self.size - 1]
self.size -= 1
self.heapifyDown(0)
return data
###########TESTING WITH A SAMPLE DATA###############
unsorted_array = [2,10,9,12,11]
obj = MinHeap(len(unsorted_array))
for element in unsorted_array:
obj.insert(element)
# Ascending Order
for i in range(len(unsorted_array)):
print(obj.removeMin())
TIME COMPLEXITY
The above diagram show the time complexity of merge sort and how it is compared with other algorithms.
Top comments (0)