Untitled
plain_text
a month ago
1.2 kB
34
Indexable
Never
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]; }