Min Heap Implementation

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
23 upvotes

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3
2 2
2 1
0
Sample Output 1 :
1
Explanation Of Sample Input 1 :
Insert 2 in the heap, and currently, 2 is the smallest element in the heap.

Insert 1 in the heap and now the smallest element is 1.

Return the smallest element, which is 1.
Sample Input 2 :
5
2 5
2 43
2 15
1 2
0
Sample Output 2 :
15
Explanation Of Sample Input 2 :
Insert 5 in the heap.
Insert 43 in the heap.
Insert 15 in the heap.

Remove element at index 2 i.e. X from the heap.

Return the smallest element, which is 15.
Constraints :
1 <= N <= 10^5
1 <= X <= 50

Time Limit: 1 sec
Hint

Complete Binary Tree with the top element as the smallest element.

Approaches (1)
Implementation

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 )

  1. Return 2*k+1.

 

right ( k )

  1. Return 2*k+2.
     

parent ( k )

  1. Return ( k-1 ) / 2.
     

heapify ( k)

  1. Find the left child of the node.
  2. Find the right child of the node.
  3. Find the smallest element between the current node and its children.
  4. Check if the left child is the smallest.
  5. Check if the right node is smallest than the previous smallest.
  6. If the smallest element is not in the current node.
  7. We have to heapify the Heap to take that element to the top.
    1. Swap the values of the current node and the smallest node value.
    2. Call the heapify function on the smallest value node which now contains the value of the parent node.

 

insert( Val )

  1. Insert a val in the heap.
  2. The function contains heap array, val to inserted.
  3. Insert the val at the end of the heap.
  4. If there is more than 1 node in the Heap.
  5. MinHeapify the heap by checking the val at its parent node.
  6. Also, do it until the heap property is not satisfied.
  7. while( i != 0 and heap[parent(i)] > heap[i]):
    1. Swap the value of the current node with its parent.
    2. Check the same if the parent element of the current element is satisfying the heap property.
    3. i = parent(i)

 

removeMin()

  1. Check if the current node is the only node in the heap.
    1. Reduce the size of the heap and return.
  2. Take out the min value and remove it from the heap.
  3. Put the last node on the top of the heap. So that we can heapify from the root node till the last children.
  4. Decrease the size of the heap as the minimum element is removed.
  5. Heapify the heap to satisfy the heap property.

minElement()

  1. Return the topmost element from the heap.
Time Complexity

O( N * log( N )), Where ‘N’ is the number of queries.


We are iterating over each query which is ‘N’ and for each insert or remove we do heapify operation where we each time go to child or parent which is at its double or half of the current position respectively and max, we will go to the height of the tree which is log ( N ).

Hence the time complexity will be O( N * log( N )).

Space Complexity

O( N ), Where ‘N’ is the number of queries.


We are creating a heap array of size ‘N’.

Hence the space complexity will be O( N ).

Code Solution
(100% EXP penalty)
Min Heap Implementation
Full screen
Console