/**
Suponga que los elementos de un heap tienen dos campos. Uno de ellos, dato, toma valores en el rango
[0..M − 1], siendo M una constante conocida, y se puede asumir que en el heap no hay dos elementos con
el mismo valor de dato. El otro campo, orden, es el que determina el orden del heap. A las operaciones de
heap se quiere agregar otra que, a un elemento identificado por su valor dato le modifica su valor orden y
restablece la condición de orden del heap.
Adapte las estructuras y algoritmos para que el orden de crecimiento del tiempo de ejecución en el peor caso
de la nueva operación sea, igual que el de las operaciones que insertan y eliminan elementos, O(log n).
**/
#include <iostream

#define M 100

struct tipo_h{
    uint dato;
    int orden;
}

struct estructura_h{
    tipo_h heap[M+1]; //arreglo que contiene elementos de tipo tipo_h y esta ordenado segun "orden", la posicion 0 no se utiliza porque usamos ix2 y ix2+1 para saber la pos de los hijos y con 0 da 0
    uint tope;
    uint posiciones[M]; //la posicion en el heap que esta el dato, ej. en el indice 0 esta la posicion en el heap del dato 0  
}


void filtradoAscendente(estructura_h &h, uint pos){
    while ((pos>1) && h.heap[pos/2].orden > h.heap[pos].orden){
        T aux= h.heap[pos];
        h.heap[pos]=h.heap[pos/2];
        h.posiciones[h.heap[pos].dato]=pos/2
        h.heap[pos/2]=aux;
        h.posiciones[h.heap[pos/2].dato]=pos;
        pos/=2;
    }  
}


void filtradoDescendente(estructura_h &h, uint pos){
    while (2*pos<=h.tope){ //verifico que tenga hijos para comparar
        int pos_hijo=2*pos;
        if ((pos_hijo + 1 <= h.tope) && (h.heap[pos_hijo].orden>(h.heap[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 (h.heap[pos_hijo].orden<(h.heap[pos].orden){
            T aux= h.heap[pos];
            h.heap[pos]=h.heap[pos_hijo];
            h.posiciones[h.heap[pos].dato]=pos_hijo
            h.heap[pos_hijo]=aux;
            h.posiciones[h.heap[pos_hijo].dato]=pos;
            pos=pos_hijo;
        }
    }
}

//Ver que no este lleno y checkear que el elemento no exista 
void insertar(estructura_h &h, tipo_h elem){
    if (h.tope<M && h.posiciones[elem.dato]==0){ //si la pos es 0 (no se usa en el heap) entonces no existe en el heap
        h.tope++;
        h.heap[h.tope]=elem;
        h.posiciones[elem.dato]=h.tope;
        filtradoAscendente(h, h.tope);
    }
}

void eliminarMin(estructura_h &h){
    if (h.tope>0){ //para ver que haya elementos
        posiciones[h.heap[1].dato]=0; //ponemos en 0 la posicion para que se sepa que ya no pertence al heap
        h.heap[1]=h.heap[h.tope];
        h.posiciones[h.heap[1].dato]=1;
        h.tope--;
        if (h.tope>0){ //si no quedo vacio dsp de eliminar el minimo
             filtradoDescendente(h, 1);
        }
    }
}

void iniciarEstructura(estructura_h &h){
    h.tope=0;
    for (int i=0; i<M; i++){ //porque al principio ningun elemento pertenece al heap
        h.posiciones[i]=0;
    }
}

void modificarOrden(estructura_h &h, uint dato, int orden){
    uint pos = h.posiciones[dato];
    int orden_anterior=h.heap[pos].orden;
    h.heap[pos].orden=orden;
    if (orden_anterior<orden){
        filtradoDescendente(h,pos);
    } else if (orden_anterior>orden) {
        filtradoAscendente(h,pos);
    }
}


int main()
{
    std::cout<<"Hello World";

    return 0;
}