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

int rodzic(int i);
int lewy(int i);
int prawy(int i);
int *kopiec_wstaw(int *A, int key, int *kopiec_rozmiar);
void kopiec_drukuj(int *A, int kopiec_rozmiar);
int *kopiec_przywroc(int *A, int kopiec_rozmiar, int i);
int *kopiec_usun_max(int *A, int *kopiec_rozmiar);

int main()
{
	int *A;
	char z = ' ';
	int key = 0;
	int kopiec_rozmiar = 0;
	A = NULL;

	while(1)
	{
		printf("Wybierz opcje:");
		printf("\nw - wstaw");
		printf("\nd - drukuj");
		printf("\nu - usun\n\n");

		fflush(stdin);
		z = getchar();

		switch(z)
		{
			case 'w':
			{
				printf("\nPodaj wartosc: ");
				fflush(stdin);
				scanf("%d", &key);
				A = kopiec_wstaw(A, key, &kopiec_rozmiar);
				printf("\n");
				break;
			}
			case 'd':
			{
				kopiec_drukuj(A, kopiec_rozmiar);
				printf("\n");
				printf("\n");
				break;
			}
			case 'u':
			{
				A = kopiec_usun_max(A, &kopiec_rozmiar);
				printf("\n");
				break;
			}
		}
	}
	return 0;
}

int rodzic(int i)
{

	return (i-1) /2;
}

int lewy(int i)
{
	return (2 * i) + 1;
}

int prawy(int i)
{
	return (2 * i) + 2;
}

int *kopiec_wstaw(int *A, int key, int *kopiec_rozmiar)
{
	int i = 0;

	*kopiec_rozmiar += 1;

	if(*kopiec_rozmiar == 1)
		A = (int *) malloc(sizeof(int));
	else
		A = (int*) realloc(A, *kopiec_rozmiar * sizeof(int));
	i = *kopiec_rozmiar - 1;

	while (i > 0 && A[rodzic(i)] < key)
	{
		A[i] = A[rodzic(i)];
		i = rodzic(i);
	}

	A[i] = key;

	return A;
}

int *kopiec_przywroc(int *A, int kopiec_rozmiar, int i)
{
	int l, r, max, temp;

	l = lewy(i);
	r = prawy(i);
	if (l <= kopiec_rozmiar - 1 && A[l] > A[i])
		max = l;
	else max = i;

	if(r <= kopiec_rozmiar - 1 && A[r] > A[max])
		max = r;
	if(max != i)
	{
		temp = A[i];
		A[i] = A[max];
		A[max] = temp;
		A = kopiec_przywroc(A, kopiec_rozmiar, max);
	}
}

int *kopiec_usun_max(int *A, int *kopiec_rozmiar)
{
	int max;

	if(*kopiec_rozmiar < 1) printf("\nKopiec pusty.");
	else
	{
		max = A[0];
		A[0] = A[*kopiec_rozmiar-1];
		*kopiec_rozmiar -= 1;
		kopiec_przywroc(A, *kopiec_rozmiar, 0);
	}
	return A;
}

void kopiec_drukuj(int *A, int kopiec_rozmiar)
{
	int i;

	printf("\n");
	for (i=0; i < kopiec_rozmiar; i++)
	{
		printf("%d, ",A[i]);
	}
}