Last Updated: 22 Jun, 2022
Min Heap Implementation
Moderate
Implement the Min Heap data structure.
Min heap is a tree data structure where the root element is the smallest of all the elements in the heap. Also, the children of every node are smaller than or equal to the root node.
The insertion and removal of elements from the heap take log('N'), where 'N' is the number of nodes in the tree.
Implement the “minHeap” class. You will be given the following types of queries:-
0 extractMinElement(): Remove the minimum element present in the heap, and return it.
1 deleteElement( i ): Delete the element present at the 'i' th index.
2 insert( key ): Insert the value 'key' in the heap.
For queries of types 0 and 1, at least one element should be in the heap.
Input Format :
The first line will contain a single integer 'N', the number of queries.
Then each of the following ‘N’ lines contains queries of the following type:-
0
1 X
2 X
Where 'X' is some value and 0, 1, and 2 are the respective values as shown in the queries above.
Output format :
Print the output of each query if there is some output.
Note :
The input will contain at least one operation of type 1.
You don't need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The heap property is satisfied by the heap data structure. And follows the properties of a complete binary tree. Heap property is as follows, which we have used all over the approach:-
Each parent element is smaller than or equal to its child elements.
As we all know, the complete binary tree is a tree with every level filled and all nodes as far left as feasible. The last level of the binary tree may be empty and unfilled.
You're probably wondering what the heap property is.
Every node of the tree is given a key value or weight in the heap data structure.
Now, the key value of the root node is compared with the values of children's nodes, and then the tree is arranged into two categories, respectively i.e., max Heap or min-heap. This data structure is used as a sorting algorithm to sort the elements in a list and an array. This sorting algorithm can be used in data structures like order statistics, priority queues, Dijkstra's algorithm, or Prim's algo. Heapify refers to creating a heap data structure using a binary tree. To create the Min-Heap, the heapify process is used. For a complete binary tree, the left child in an array is 2*i+1 and the right child is 2*i+2 if the current node index is ‘i’ in the array. For the index ‘i’ the parent of it is (i-1)/2.
Now to create min-heap following steps are used:-
left ( k )
- Return 2*k+1.
right ( k )
- Return 2*k+2.
parent ( k )
- Return ( k-1 ) / 2.
heapify ( k)
- Find the left child of the node.
- Find the right child of the node.
- Find the smallest element between the current node and its children.
- Check if the left child is the smallest.
- Check if the right node is smallest than the previous smallest.
- If the smallest element is not in the current node.
- We have to heapify the Heap to take that element to the top.
- Swap the values of the current node and the smallest node value.
- Call the heapify function on the smallest value node which now contains the value of the parent node.
insert( Val )
- Insert a val in the heap.
- The function contains heap array, val to inserted.
- Insert the val at the end of the heap.
- If there is more than 1 node in the Heap.
- MinHeapify the heap by checking the val at its parent node.
- Also, do it until the heap property is not satisfied.
- while( i != 0 and heap[parent(i)] > heap[i]):
- Swap the value of the current node with its parent.
- Check the same if the parent element of the current element is satisfying the heap property.
- i = parent(i)
removeMin()
- Check if the current node is the only node in the heap.
- Reduce the size of the heap and return.
- Take out the min value and remove it from the heap.
- Put the last node on the top of the heap. So that we can heapify from the root node till the last children.
- Decrease the size of the heap as the minimum element is removed.
- Heapify the heap to satisfy the heap property.
minElement()
- Return the topmost element from the heap.