#include  <stdio.h>
#include <stdlib.h>
#define MAX 100

void heapify(int a[MAX], int p, int n);
void buildheap(int a[MAX], int n);
int  pq_extract(int q[MAX],int *pu);
void pq_insert(int  q[MAX],int *pu, int x);

void main(void)
	{int n,scelta,i,a[MAX],x,estrai;
	 char riga[20];

	 printf("Quanti numeri vuoi inserire?\n");
	 gets(riga);
	 n=atoi(riga);
	 for(i=0;i<n;i++)
		{
		  printf("Inserisci numero:\n");
		  scanf("%d",&a[i]);
		 }
	  for(i=0;i<n;i++)printf("%d ",a[i]);
	  printf("...creo l'heap...\n\n");
	  buildheap(a,n);
	  for(i=0;i<n;i++) printf("%d ",a[i]);
	  do {printf("MENU DI SCELTA:\n");
			printf("1-Inserisci elemento\n");
			printf("2-Estrai elemento\n");
			printf("3-Esci\n");
			scanf("%d",&scelta);
		switch (scelta)
			{
			case 1: printf("Inserisci il numero che vuoi immettere nell'heap : ");
					  scanf("%d",&x);
					  pq_insert(a,&n,x);
					  break;
			case 2: estrai=pq_extract(a,&n);
						printf("l'elemento pių grande che ho estratto č %d\n",estrai);
						break;
		  }for(i=0;i<n;i++)printf("%d ",a[i]);

		 }while (scelta!=3);

	}




void heapify(int a[MAX],int p,int n)
{
  int t,s,d,max;
  s= (2*p)+1;
  d= (2*p)+2;
  max=((s<=n && a[s]>a[p]?s:p));
  max=((d<=n && a[d]>a[max]?d:max));
  if (max!=p)
	 {  t=a[max];
		 a[max]=a[p];
		 a[p]=t;
		 heapify(a,max,n);
	 }
	 }
void buildheap(int a[MAX],int n)
{ int i;
  for(i=n/2-1; i>=0;i--)
  {heapify(a,i,n-1);
	}
  }


int pq_extract(int q[MAX],int *pu)
{
 int p;
 if(*pu<0) return(NULL);
 else
  {p=q[0];
	q[0]=q[*pu-1];(*pu)--;
	heapify(q,0,*pu);
	return(p);
	}
 }
void pq_insert(int q[MAX], int *pu, int x)
{
  int i;
  *pu=*pu+1;
  i=*pu-1;
  while(i>0 && q[(i-1)/2]<x)
	 { q[i]=q[(i-1)/2];
		i=(i-1)/2;
	 }
  q[i]=x;
}