Untitled

unknown
plain_text
a year ago
1.8 kB
6
Indexable
Never
``` #include<vector>

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++){
}

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

```