#include<iostream>
using namespace std;
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
class maxheap{
int *harr;
int capacity;
public:
int heapsize;
maxheap(int i)
{
capacity=i;
heapsize=0;
harr=new int[capacity];
}
int parent(int i)
{
return((i-1)/2);
}
int left(int i)
{
return ((2*1)+1);
}
int right(int i)
{
return ((2*i)+2);
}
void insert(int i)
{
if(heapsize==capacity)
{
cout<<"nheap is full, Not Addingn";
return;
}
heapsize++;
int k=heapsize-1;
harr[k]=i;
while(k!=0 && harr[parent(k)]<harr[k])
{
swap(&harr[i],&harr[parent(i)]);
k=parent(k);
}
}
int extractmax()
{
if(heapsize<=0)
{
exit(0);
}
if(heapsize==1)
{
heapsize--;
return harr[0];
}
int root=harr[0];
harr[0]=harr[heapsize-1];
heapsize--;
heapify(0);
return root;
}
void heapify(int i)
{
int l=left(i);
int r=right(i);
int greatest=i;
if(l<heapsize && harr[l]>harr[greatest])
{
greatest=l;
}
if(r<heapsize && harr[r]>harr[greatest])
{
greatest=r;
}
while(greatest!=i)
{
swap(&harr[i],&harr[greatest]);
heapify(greatest);
}
}
void deletee(int index)
{
increasevalue(index,INT_MAX);
extractmax();
}
void increasevalue(int i,int val)
{
harr[i]=val;
while(i!=0 && harr[parent(i)]<harr[i])
{
swap(&harr[i],&harr[parent(i)]);
i=parent(i);
}
}
};
int main()
{
int n,choice,item;
cout<<"enter the size of heap";
cin>>n;
maxheap h(n);
while(1)
{
cout<<"n1.Insert a vlauen2.to extract the maximum valuen3. Heap sort/n4.delete value n5.exit";
cin>>choice;
switch(choice)
{
case 1:
cout<<"nenter the value to be insertedn";
cin>>item;
h.insert(item);
break;
case 2:
cout<<"n The maximum value of the heap is "<<h.extractmax();
break;
case 3:
cout<<"nheap sortnn";
while(h.heapsize!=0)
{
cout<<h.extractmax()<<"t";
h.heapsize--;
}
break;
case 4:
cout<<"enter the index to be deleted";
cin>>item;
h.deletee(item);
break;
case 5:
exit(0);
}
}
return 0;
}
0 Comments