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