Untitled

void addheap(int val, vector<int>&heap){ //MAXHEAP
    heap.push_back(val);
    int size=heap.size();
    
    int i=size-1;
    while(i>1){
        int p=i/2;
        if(heap[i]>heap[p]){
            swap(heap[i],heap[p]);
            i=i/2;
        }else{
            break;
        }
    }
}

void correct(vector<int>&heap){
    int size=heap.size();
    int i=1;
    while(i<size){
        int li=2*i;
        int ri=2*i+1;

        if(li<size && heap[i]<heap[li]){
            swap(heap[i],heap[li]);
            i=li;
        }else if (ri<size && heap[i]<heap[ri]){
            swap(heap[i],heap[ri]);
            i=ri;
        }else{
            return;
        }
    }
}


int kthSmallest(int n,int k,vector<int> Arr)
{
    vector<int> heap;
    heap.push_back(-1);

    for(int i=0;i<k;i++){
        addheap(Arr[i],heap);
    }

    for(int i=k;i<n;i++){
        if(Arr[i]<heap[1]){
            heap.erase(heap.begin()+1);  //HERE SIZE WONT CHANGE AS WE ARE REMOVING
            heap.insert(heap.begin()+1,Arr[i]);//1st element and inserting arr[i]
            correct(heap);
        }
    }
    return heap[1];
}