#include <stdio.h>
#include <stdlib.h>
#include <conio.h>


int left(int i);
int right(int i);
int parent(int i);


void kopiec_przywroc(int*k,int n,int i);
void kopiec_buduj(int* k,int n);
int kopiec_usun_max(int* k,int* n);
int kopiec_wstaw(int* k, int* n,int i);


void main(){
	char w='\0';

	int a,n,i,*tab=NULL;
	
			
			while(1){	
				printf("Kopce\n");

		printf("w-wstaw do kopca\n");
		printf("u-usun wezel\n");
		printf("b-buduj kopiec\n");
	
		printf("q-wyjscie\n");
		printf("Co chcesz zrobic:");
			fflush(stdin);
			scanf("%c",&w);
	switch(w){
		
		case 'b':
			printf("Podaj ilosc elementow z ktorych chcesz zbudowac kopiec:");
			fflush(stdin);
			scanf("%d",&n);
			if(n<=0){
				printf("Blad");
				break;
			}
			tab=(int*)malloc(n*sizeof(int));
			for(i=0;i<n;i++){
				scanf("%d",&a);
				*(tab+i)=a;
			}
			kopiec_buduj(tab,n);
			for(i=0;i<n;i++)
				printf("%d;",*(tab+i));
				
			break;
		case 'u':
			
			kopiec_usun_max(tab,&n);
			for(i=0;i<n;i++)
				printf("%d;",*(tab+i));

			break;
		case 'w':
			printf("Podaj wartosc elementu do wstawienia:");
			fflush(stdin);
			scanf("%d",&a)
			kopiec_wstaw(tab,&n,a);
			for(i=0;i<n;i++)
				printf("%d;",*(tab+i));
			break;
		case 'q':
			free(tab);
			break;
		default:
			printf("Błedne polecenie\n");

	}
	getch();
	system("cls");
			}
	
}

int left(int i){
	return 2*i+1;
}
int right(int i){
	return 2*i+2;
}
int parent(int i){
	return (i-1)/2;
}


void kopiec_przywroc(int* k,int n,int i){
	int l,r,max,tmp;
	l=left(i);
	r=right(i);
	if(l<n && *(k+l)>*(k+i)){
		max=l;
	}else{
		max=i;
	}
	if(r<n && *(k+r)>*(k+max)){
		max=r;
	}
	if(max!=i){
		tmp=*(k+max);
		*(k+max)=*(k+i);
		*(k+i)=tmp;
		kopiec_przywroc(k,n,max);
		
	}
}
void kopiec_buduj(int* k,int n){
	int i=(n-1)/2;
	while(i>=0){
		kopiec_przywroc(k,n,i);
		i--;
	}
}

int kopiec_usun_max(int* k,int* n){
	int max=*k;
	*k=*(k+*n);
	*n=*n-1;
	kopiec_przywroc(k,n,0);

}
int kopiec_wstaw(int* k, int* n,int key){
	int i;
	*n=*n+1;
	i=*n;
	while(i>0 && *(k+parent(i))<key){
		*(k+i)=*(k+parent(i))
		i=parent(i);
	}
	*(k+i)=key


}