Untitled
unknown
plain_text
a year ago
1.8 kB
6
Indexable
Never
#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]; }