/*
Desarrolle implementaciones completas del TAD Cola de Prioridad, utilizando:
I. Listas ordenadas de nodos enlazados para la versión no acotada del TAD.
II. Árboles Parcialmente Ordenados implementados sobre un arreglo (Montículo o Heap) para la versión acotada del TAD.
*/

//Version acotada

//Retorna una cola de prioridad vacia de elementos de tipo T de tamano maximo cota
ColaPrio CrearCP(int cota);

//Retorna true si y solo la cola de prioridad cp esta llena
bool estaLlenaCP(ColaPrio cp);

//Inserta en la cola de prioridad cp un elemento de tipo T con prioridad p
//Si la prioridad p se repite hay que establecer un criterio de "desempate" (ej. prioritario el que se inserto primero)
//Si el elemento T se repite no habria problema
//PRE: !estaLlenaCP()
void insertarCP(ColaPrio &cp, int p, T elemento);

//Retorna el elemento prioritario de la cola de prioridad cp
// Pre: !esVaciaCP
T priotarioCP(ColaPrio cp);

//Elimina de la cola de prioridad cp el elemento prioritario y libera su memoria asociada
// Si esVaciaCP() entonces no tiene efecto
void eliminarPrioritario(ColaPrio &cp);

//Retorna true si y solo si la cola de prioridad es vacia
bool esVaciaCP();


struct tipo_h{
    T dato;
    int orden;
}

struct heap {
    int tope;
    int tamano_max;
    tipo_h* arreglo;
}

typedef heap * ColaPrio;

//Cola de prioridad de tamaño máximo M elementos
ColaPrio CrearCP(int M){
    ColaPrio nuevo = new heap;
    nuevo->tope=0;
    nuevo->tamano_max=M;
    nuevo->arreglo= new tipo_h[M+1]; //porque la primera pos no la usamos
    return nuevo;
}

bool estaLlenaCP(ColaPrio cp){
    return cp->tamano_max==cp->tope;
}

bool esVaciaCP(ColaPrio cp){
    return cp->tope==0;
}

void filtradoAscendente(tipo_h* arreglo, int pos){
    while ((pos>1) && arreglo[pos/2].orden > arreglo[pos].orden){
        tipo_h aux= arreglo[pos];
        arreglo[pos]=arreglo[pos/2];
        arreglo[pos/2]=aux;
        pos/=2;
    }
}

void filtradoDescendente(tipo_h* arreglo, int n, int pos){
    while (2*pos<=n){ //verifico que tenga hijos para comparar
        int pos_hijo=2*pos;
        if ((pos_hijo + 1 <= n) && (arreglo[pos_hijo].orden>arreglo[pos_hijo+1].orden)) { // si el hijo der existe y a su vez es mas prioritario que el izq, entonces tengo que switchear con ese
            pos_hijo=pos_hijo+1;
        }
        if (arreglo[pos_hijo].orden<arreglo[pos].orden){
            tipo_h aux= arreglo[pos_hijo];
            arreglo[pos_hijo]=arreglo[pos];
            arreglo[pos]=aux;
            pos = pos_hijo;
        }
    }
}


void insertarCP(ColaPrio &cp, int p, T elemento){
    if (!estaLlenaCP(cp)){
        tipo_h nuevo;
        nuevo.dato=elemento;
        nuevo.orden=p;
        cp->tope++;
        cp->arreglo[cp->tope]=nuevo;
        filtradoAscendente(cp->arreglo,cp->tope);
    }
}

//PRE: !esVaciaCP(cp)
T priotarioCP(ColaPrio cp){
    return cp->arreglo[1].elemento;
}

void eliminarPrioritario(ColaPrio &cp){
    if (!estaVaciaCP(cp)){
        cp->arreglo[1]=cp->arreglo[cp->tope];
        cp->tope--;
    }
    if (!estaVaciaCP(cp)){//dada nuestra implementacion de filtradoDescendente no hay problema si estuviera vacia CP, por lo cual no seria necesario el if
        filtradoDescendente(cp->arreglo, cp->tope, 1);
    }
}


#include <stdio.h>


int main()
{
    printf("Hello World");

    return 0;
}