Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ayuda del ejercicio 1.a del tema 4

Puedes completar y programar en C++ lo que falta a continuación:

#include <queue> // Para usar priority_queue

Huffman::Nodo::Nodo(char c, float f)
  : caracter{c}, frecuencia{f}, izquierdo{nullptr}, derecho{nullptr}, padre{nullptr} {
}

Huffman::Huffman(const vector< pair<char, float> > & frecuencias) {

   if (frecuencias.size() < 2)
      throw string("Necesitamos al menos dos caracteres con sus frecuencias.");

   class ComparadorNodos { // La podemos poner aqui para usarla en este metodo
                           // y que tenga acceso a la parte privada de Huffman
   public:
      // ...
   };

   priority_queue<Nodo *, vector<Nodo *>, ComparadorNodos> colaPrioridad;


   Para cada caracter y frecuencia en el vector frecuencias :
      Crear un nodo que contenga ese caracter y frecuencia
      Insertar la direccion de ese nodo en la cola de prioridad
      Insertar la direccion de ese nodo en el diccionario hojas usando el caracter como clave

   Mientras la cola de prioridad contenga mas de un elemento :
      Extraer de la cola de prioridad los dos elementos de menor prioridad
      Crear un nuevo nodo que tenga a esos dos como hijos
      Completar el resto de atributos de esos nodos
      Insertar la direccion del nuevo nodo en la cola de prioridad

   Asignar al atributo raiz el elemento restante en la cola de prioridad

}