20201104 Clase Heap(string) implementada con vectores

#include <iostream>
using namespace std;

class Heap {
public:
    /** Default constructor */
    Heap();
    /** Default destructor */
    virtual ~Heap();
    void agregar(string, int);  //agrega elemento , prioridad
    string extraer();  //solo retorna el elemento
    bool vacio();
protected:
private:
    class DatoPrivado {
    public:
        string nombre;
        int prioridad;
        int dato;
    };
    static const int MAX = 100;
    DatoPrivado Vector[MAX];
    int Ultimo;
    void Subir();
    void Bajar();
};

/**IMPLEMENTACION**/
Heap::Heap()  {
    Ultimo = 0;
}

Heap::~Heap() {
}

bool Heap::vacio() {
    return (Ultimo == 0);
}

void Heap::Subir() {
    /**En el método flotar(SUBIR) el nodo dado se compara con su nodo
    padre y se realiza el intercambio si éste es mayor que el padre,
    iterando este paso mientras sea necesario*/
    int k, i;
    DatoPrivado aux;
    aux = Vector[Ultimo];
    Vector[0] = Vector[Ultimo];
    i = Ultimo; /**Última Posicion**/
    k = i/2; /**posición del padre**/
    /**Recorre el arreglo hasta que organiza las prioridades**/
    /**Mientras el padre sea mayor que el hijo**/
    while (Vector[k].prioridad > aux.prioridad) {
        //Al hijo le asigno la posición del padre
        Vector[i] = Vector[k];
        i = k; //Posición del Padre Anterior
        k = i/2; //Posición del nuevo padre
    }
    //nueva Posición del padre
    Vector[i] = aux;
}

void Heap::Bajar() {
    bool fin;
    DatoPrivado aux;
    aux = Vector[1];
    int k = 1;
    int i = k*2;
    fin = false;

    while ((k <= Ultimo/2)&&(!fin)) {
        if(i < Ultimo) {
            if(Vector[i+1].prioridad < Vector[i].prioridad)
                i++;
        }

        if(aux.prioridad > Vector[i].prioridad) {
            Vector[k] = Vector[i];
            k = i;
            i = k*2;
        }
        else
            fin = true;
    }
    Vector[k] = aux;
}

void Heap::agregar(string intDato, int intPrioridad) {
    /**¿Cómo añadir un nuevo elemento?
    1 Colocar el nuevo elemento como último elemento del montículo(Heap), justo a la derecha del último o como primero de un nuevo nivel.
    2 Reestablecer el orden de montıculo flotando(Subiendo) el elemento recién añadido
    En el método flotar(SUBIR) el nodo dado se compara con su nodo padre y se realiza el intercambio si éste es mayor que el padre,
    iterando este paso mientras sea necesario
    */
    DatoPrivado aux;
    aux.prioridad   = intPrioridad;
    aux.nombre        = intDato;
    Ultimo++;
    Vector[Ultimo] = aux;
    Subir();
}

string Heap::extraer() {
    string x = Vector[1].nombre;
    Vector[1] = Vector[Ultimo];
    Ultimo--;
    Bajar();
    return x;
}

void imprimir(int A[], int n){
    int i;
    cout << "arreglo..." << endl;
    for(i=0; i<n; i++)
        cout << "Arreglo[" << i << "] = " << A[i] << endl;
}

int main() {

    cout << "[Heap]" << endl;
    Heap h;
    h.agregar("Hector " ,10);
    h.agregar("Maria " ,1);
    h.agregar("Pedro" ,5);
    h.agregar("Don Juan " ,3);
    h.agregar("Rogelio " ,10);
    h.agregar("Roberto " ,10);
    h.agregar("Marco " ,10);
    h.agregar("Rosa" ,1);
    h.agregar("Viviana " ,2);

    while(!h.vacio()){
        cout << h.extraer() << endl;
    }

    return 0;

}