#include<iostream>//minheap
using namespace std;
void swap(int *x,int *y);
class heap
{
int *harr;
int capacity;
int heapsize;
public:
heap(int cap)
{
heapsize=0;
capacity=cap;
harr=new int[cap];
}
int parent(int i)
{
return ((i-1)/2);
}
int left(int i)
{
return(2*i+1);
}
int right(int i)
{
return (2*i+2);
}
void heapify(int i)//adjusting values to fullfill the properties of heap
{
int l=left(i);
int r=right(i);
int smallest=i;
if(l<heapsize && harr[l]<harr[smallest])
{
smallest=l;
}
if(r<heapsize && harr[r]<harr[smallest])
{
smallest=r;
}
if(smallest !=i)
{
swap(&harr[i], &harr[smallest]);
heapify(smallest);
}
}
int extractmin()
{
if(heapsize<=0)
{
return INT_MAX;
}
if(heapsize==1)
{
heapsize--;
return harr[0];
}
int root=harr[0];
harr[0]=harr[heapsize-1];
heapsize--;
heapify(0);
return root;
}
int getmin()
{
return harr[0];
}
void insert(int k)
{
if(heapsize==capacity)
{
cout<<"nheap is fulln";
return;
}
heapsize++;
int i=heapsize-1;
harr[i]=k;
while(i!=0 && harr[parent(i)]>harr[i])
{
swap(&harr[i],&harr[parent(i)]);
i=parent(i);
}
}
void decreasevalue(int i,int val)
{
harr[i]=val;
while(i!=0&&harr[parent(i)]>harr[i])
{
swap(&harr[i],&harr[parent(i)]);
i=parent(i);
}
}
void deletee(int i)
{
decreasevalue(i,INT_MIN);
extractmin();
}
};
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
int main()
{
heap h(11);
h.insert(3);
h.insert(2);
h.deletee(0);
h.insert(15);
h.insert(5);
h.insert(4);
h.insert(45);
cout << h.extractmin() << " ";
cout << h.getmin() << " ";
return 0;
}
0 Comments