/*
    Esteban Ordano
    heap.c
    26 de Agosto 2009
*/

#include <stdio.h>
#define MAX_VAL 1<<18

int N;
int H[MAX_VAL];

void iniciar_heap();
int agregar(int numero);
int minimo();
int menu();         // Esta funci\'on devuelve el valor que se debe agregar o 0x10000000
                    // para salir o 0x10000001 para pedir el valor minimo de la heap

int
main()
{
    int respuesta = 0;
    iniciar_heap();

    while(1)
    {
        respuesta = menu();
        if (respuesta == 0x10000000)
        {
            break;
        }
        else if (respuesta == 0x10000001)
        {
            if (N <= 1)
            {
                printf("Su Heap no tiene elementos.\n");
            }
            else
            {
                printf("Obtenido el valor %d.\n", minimo());
            }
        }
        else if (respuesta == 0x10000002)
        {
            printf("Su heap tiene tama\'no %d\n", N);
        }
        else
        {
            if (agregar(respuesta))
            {
                printf("Agregado el valor %d a la Heap.\n", respuesta);
            }
            else
            {
                printf("Ha ocurrido un error.\n");
            }
        }
    }

    return 0;
}

int
menu()
{
    int pedido = 0, temp = 0;

    while(pedido > 4 || pedido < 1)
    {
        printf("  Ingrese acci\'on: \n");
        printf("      *Agregar valor a la heap (1)\n");
        printf("      *Tomar el menor elemento de la heap (2)\n");
        printf("      *Consultar el tama\'no de la heap (3)\n");
        printf("      *Salir (4)\n");

        scanf("%d", &pedido);

        if (pedido > 4 || pedido < 1)
        {
            printf("Lo lamento, s\'olo entiendo valores num\'ericos naturales");
            printf(" entre el 1 y el 4. \n\n");
        }
    }

    switch(pedido)
    {
        case 1:
            printf("Ingrese el valor: \n");
            scanf("%d", &pedido);                 // Reuso la variable pedido
            return pedido;
        case 2:
            return 0x10000001;
        case 3:
            return 0x10000002;
        default:
            break;
    }
    return 0x10000000;
}

void
iniciar_heap()                     // Constructor
{
    N = 1;
}

int
minimo()                           // Funci\'on para obtener el m\'inimo
{
    // Guarda el valor de retorno
    int respuesta = H[1], n = 1, temp = 0, selected = 0;

    // Asigna el valor del \'ultimo elemento al root (ahora eliminado)
    // y disminuye el tama\'no de la heap
    H[1] = H[--N];

    // y heapifica para abajo
    while(n<<1 < N)
    {
        if ((n<<1)+1 < N)
        {
            if (H[n] > H[n<<1] && H[n<<1] < H[(n<<1)+1])
            {
                temp = H[n];
                H[n] = H[n<<1];
                H[n<<1] = temp;
                selected = 0;
            }
            else if (H[n] > H[(n<<1)+1])
            {
                temp = H[n];
                H[n] = H[(n<<1)+1];
                H[(n<<1)+1] = temp;
                selected = 1;
            }
        }
        else
        {
            if (H[n] > H[n<<1])
            {
                selected = 0;
                temp = H[n];
                H[n] = H[n<<1];
                H[n<<1] = temp;
            }
        }
        n = (n<<1)+selected;
    }
    return respuesta;
};

int
agregar(int numero)
{
    int temp = 0, n = 0;

    if (N == MAX_VAL)
    {
        return 0;
    }

    // Guarda el valor n en el \'ultimo elemento y heapifica
    H[N++] = numero;
    n = N-1;
    while(n>>1 > 0 && H[n>>1] > H[n])
    {
        temp = H[n>>1];
        H[n>>1] = H[n];
        H[n] = temp;
        n >>= 1;
    }
    return 1;
};