Untitled

 #include<vector>

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

/* void correct(vector<int>&heap){  //this is deletion code not heapify code
    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;
        }
    }
} */

void correct(vector<int>& heap,int i,int n){ //HEAPIFY ALGO
    int largest=i;  // the algo makes sure that all nodes including and below i are heapified
    int li=2*i+1;
    int ri=2*i+2;

    if(li<n && heap[largest]<heap[li]){
        largest=li;
    }

    if(ri<n && heap[largest]<heap[ri]){
        largest=ri;
    }

    if(largest!=i){
        swap(heap[largest],heap[i]);
        i=largest;
        correct(heap,largest,n);
    }
}


int kthSmallest(int n,int k,vector<int> Arr)
{
    vector<int> heap;

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

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