Min Heap

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 its child elements.

The complete binary tree, as we all know, is a tree with every level filled and all nodes as far left as feasible. It's possible that the last level of the binary tree is 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 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 ( heap, 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( heap, 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)

extractMin( heap )

1. Check if the current node is the only node in the heap.
   1. Return heap[0].
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 heap as the minimum element is removed.
5. Heapify the heap to satisfy the heap property.

minHeap ( N, Q )

1. Define minHeap function which takes the size of Queries and Queries as Input.
2. Returns an array of outputs depending on the queries.
3. Define a heap array to store elements.
4. Define an array that stores the min elements.
5. For each query in the array Q.
6. If the query is of type 1 then insert the value in the heap.
7. Else take min element from the heap and append it in the ans.
8. Return the ans array.

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 at max, we will go to the height of the tree which is log ( N ).

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

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 ).