For this Question: A binary heap is a Binary Tree with following properties:
1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

Given some queries and your task is to implement the three methods insertKey,  deleteKey,  and extractMin on a Binary Min Heap and call them as per the query given below:


1) 1  x  (a query of this type means to insert an element in the min heap with value x )
2) 2  x  (a query of this type means to remove an element at position x from the min heap)
3) 3  (a query like this removes the min element from the min heap and prints it ).The first line of the input contains an integer 'T' denoting the number of test cases. Then T test cases follow. First line of each test case contains an integer Q denoting the number of queries. The second line of each test case contains Q queries separated by space.


Constraints:
1 <= T <= 100
1 <= Q <= 100
1 <= x <= 100The output for each test case of query 3 will be space separated integers having -1  if the heap is empty else the min element of the heap. Sample Input:
2
7
1 4 1 2 3 1 6 2 0 3 3
5
1 8 1 9 2 1 3 3

Sample Output:
2 6 -1
8 -1
 

Explanation:
Testcase 1:
In the first test case for query 
1 4 the heap will have {4}  
1 2  the heap will be {2 4}
3 removes min element from heap ie 2 and prints it now heap is {4} 
1 6 inserts 6 to heap now heap is {4 6}
2 0 delete element at position 0 of heap now heap is {6}
3 remove min element from heap ie 6 and prints it  now the heap is empty {}
3 since heap is empty thus no min element exist so -1 is printed ., I have written this Solution Code: // Initial Template for C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

// Structure for Min Heap
struct MinHeap {
    int *harr;
    int capacity;
    int heap_size;

    // Constructor for Min Heap
    MinHeap(int c) {
        heap_size = 0;
        capacity = c;
        harr = new int[c];
    }

    ~MinHeap() { delete[] harr; }

    int parent(int i) { return (i - 1) / 2; }

    int left(int i) { return (2 * i + 1); }

    int right(int i) { return (2 * i + 2); }

    void MinHeapify(int); // Implemented in user editor
    int extractMin();
    void decreaseKey(int i, int new_val);
    void deleteKey(int i);
    void insertKey(int k);
};

// Position this line where user code will be pasted.

// Driver code
int main() {
    int t;
    cin >> t;

    while (t--) {
        ll a;
        cin >> a;
        MinHeap h(a);
        for (ll i = 0; i < a; i++) {
            int c;
            int n;
            cin >> c;
            if (c == 1) {
                cin >> n;

                h.insertKey(n);
            }
            if (c == 2) {
                cin >> n;
                h.deleteKey(n);
            }
            if (c == 3) {
                cout << h.extractMin() << " ";
            }
        }
        cout << endl;
        // delete h.harr;
        h.harr = NULL;
    }
    return 0;
}
// } Driver Code Ends


/*The structure of the class is
struct MinHeap
{
    int *harr;
    int capacity, heap_size;
    MinHeap(int cap) {heap_size = 0; capacity = cap; harr = new int[cap];}
    int extractMin();
    void deleteKey(int i);
    void insertKey(int k);
};*/

// You need to write code for below three functions

/* Removes min element from min heap and returns it */
int MinHeap::extractMin() {
    if(heap_size==0)
    return -1;
    if(heap_size==1)
    {
        int x=harr[0];
        heap_size=0;
        return x;
    }
    else
    {
        int x=harr[0];
        swap(harr[heap_size-1],harr[0]);
        heap_size=heap_size-1;
        MinHeapify(0);
        return x;

    }
}

/* Removes element from position x in the min heap  */
void MinHeap::deleteKey(int i) {
    if(i>heap_size-1)
    return ;
  decreaseKey(i,INT_MIN);
  extractMin();
}

/* Inserts an element at position x into the min heap*/
void MinHeap::insertKey(int k) {
    if(heap_size==capacity)
    return;
    heap_size=heap_size+1;
    harr[heap_size-1]=k;
    int i=heap_size-1;
    while(i!=0 && harr[parent(i)]> harr[i])
    {
        swap(harr[i],harr[parent(i)]);
        i=parent(i);
    }

}

// Decrease Key operation, helps in deleting key from heap
void MinHeap::decreaseKey(int i, int new_val) {
    harr[i] = new_val;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}

/* You may call below MinHeapify function in
   above codes. Please do not delete this code
   if you are not writing your own MinHeapify */
void MinHeap::MinHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i]) smallest = l;
    if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        MinHeapify(smallest);
    }
}
, In this Programming Language: C++, Now tell me if this Code is compilable or not?