#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];
}