Algoritmos y Estructuras de Datos (VJ1215)

En clase de teoría nos basaremos en los siguientes apartados de los capítulos 6 "Priority Queues (Heaps)" y 7 "Sorting" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss:

• 6.1 Model
• 6.2 Simple Implementations
• 6.3 Binary Heap
  • 6.3.1 Structure Property
  • 6.3.2 Heap-Order Property
  • 6.3.3 Basic Heap Operations
  • 6.3.4 Other Heap Operations
• 7.5 Heapsort

Veremos también estas transparencias que acompañan al libro "Algorithm Design" de Jon Kleinberg y Éva Tardos preparadas por Kevin Wayne:

• Binary heap demo (errata en p. 8 a 13: donde dice "larger" debería decir "smaller")

• Heapify demo (el algoritmo para construir un montículo con n datos en tiempo O(n) se denomina "Heapify" o "buildHeap" dependiendo del autor; no lo confundas con "Heapsort")

1. Clase de teoría TE1 17/10
   Clase de prácticas LA2 y LA4 22/10, LA1 y LA3 24/10

   Vamos a hacer un ejercicio práctico de utilización de colas de prioridad implementando el algoritmo de Huffman, que se explicará en clase de prácticas y que también nos sirve como primer ejemplo de algoritmo voraz en el tema 5.1. En su implementación haremos uso de estructuras de datos que hemos estudiado en temas anteriores. Concretamente, vamos a ver una aplicación conjunta de árboles binarios (diferentes de los árboles binarios de búsqueda), colas de prioridad y diccionarios.

   En temas anteriores hemos puesto el énfasis en aprender a realizar nuestras propias implementaciones de Tipos Abstractos de Datos. En las prácticas de este tema vamos a poner el énfasis en aprender a utilizar implementaciones estándar. Por ello, para trabajar con colas de prioridad y diccionarios, recurriremos esta vez a las clases priority_queue y map de la Biblioteca de Plantillas Estándar de C++ (Standard Template Library, conocida como STL).

   Recurso opcional La página History of the Standard Template Library de la Wikipedia describe el origen de la STL.

   Ayuda con C++: utilización de la Biblioteca de Plantillas Estándar (STL)

   La STL incluye contenedores que proporcionan implementaciones genéricas de los Tipos Abstractos de Datos más importantes (en el ejercicio 7 del tema 3 ya viste un primer ejemplo de utilización de queue):

   • Pila (stack)
   • Cola (queue)
   • Lista (list con listas enlazadas y vector con vectores)
   • Conjunto (set con árboles de búsqueda y unordered_set con tablas de dispersión)
   • Multiconjunto (multiset con árboles de búsqueda y unordered_multiset con tablas de dispersión)
   • Diccionario (map con árboles de búsqueda y unordered_map con tablas de dispersión)
   • Cola de Prioridad (priority_queue)
   • etc.

   Para conocer lo que vas a necesitar en esta práctica, mira los siguientes ejemplos. En ellos no se trata de ilustrar exhaustivamente todo lo que se puede hacer con esas clases, sino las operaciones más importantes. Compílalos, ejecútalos, y trata de entender todo lo que sucede. Puedes consultar al profesor las dudas que tengas. Haz las modificaciones que se sugieren en el código y cualquier otra que consideres conveniente.

   • Ejemplo de uso de priority_queue con enteros Clase de teoría TE1 17/10
   • Ejemplo de uso de priority_queue con objetos Clase de teoría TE1 17/10
   • Ejemplo de uso de priority_queue con punteros Clase de teoría TE1 17/10
   • Ejemplo de uso de string
   • Ejemplo de uso de pair
   • Ejemplo de uso de map

   Con esas herramientas, la práctica consiste en lo siguiente: completa la implementación de la clase Huffman que puedes encontrar en este fichero Huffman.h, añadiendo en Huffman.cpp lo necesario para que funcionen estos ejemplos de uso (la salida de tu implementación no tiene por qué ser exactamente igual, puede haber codificaciones igual de buenas que se diferencian en qué hemos elegido en el algoritmo de Huffman en caso de empate o en qué hemos puesto como hijo derecho y qué hemos puesto como hijo izquierdo):

   1. Al ejecutar EjemploHuffmanWikipedia.cpp se obtiene EjemploHuffmanWikipedia.salida.

   2. Al ejecutar EjemploHuffmanEjercicio1Tema5.cpp se obtiene EjemploHuffmanEjercicio1Tema5.salida.

   3. Al ejecutar TestHuffman.cpp se obtiene TestHuffman.salida.

   Para ello, tu implementación debe ofrecer los tres métodos públicos que se enumeran a continuación.

   1. Un constructor

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

      al que se le pasará una tabla de caracteres a codificar junto con sus frecuencias. Esa tabla es un vector de pares. Consulta este ejemplo de uso de pair para conocer eso.

      El constructor, aplicando el algoritmo de Huffman, debe construir el árbol de Huffman, dando valor a los atributos previstos en Huffman.h. Esos atributos se han elegido para poder realizar eficientemente los dos métodos de codificación y decodificación que se piden en los apartados b y c:

      • En el método decodificar entraremos al árbol por la raíz y nos moveremos hacia los hijos hasta una hoja.

        Para entrar al árbol de Huffman por la raíz en el método decodificar, disponemos del atributo raiz.

        Para movernos hacia los hijos, disponemos de los atributos izquierdo y derecho en cada nodo. Con todo ello ya has aprendido a trabajar en el tema 3 (el árbol de Hufman no es un árbol binario de búsqueda, pero sí que es un árbol binario).

      • En el método codificar entraremos al árbol por las hojas y nos moveremos hacia el padre hasta la raíz.

        Para entrar al árbol de Huffman por las hojas en el método codificar, disponemos del atributo hojas, que es un diccionario en el que cada carácter del albabeto será la clave con la que acceder a su correspondiente nodo hoja. El constructor que crea el árbol de Huffman se debe encargar también de insertar esos datos en ese diccionario. Para ello, consulta este ejemplo de uso de map y elige, de las tres formas de insertar que se ilustran ahí, la que prefieras.

        Para movernos hacia la raíz, disponemos del atributo padre en cada nodo.

        Para facilitar la codificación, en cada nodo disponemos también del atributo bit, cuyo valor será el carácter '0' si se trata de un hijo izquierdo y '1' si se trata de un hijo derecho.

      Esta descripción de la Wikipedia, en su primera lista numerada, te puede ayudar a implementar el algoritmo de Huffman.

      Ayuda con C++: caracteres y cadenas

      En C++ los literales de tipo carácter se encierran entre comillas simples, mientras que los literales de tipo cadena se encierran entre comillas dobles. Las cadenas, como casos particulares, pueden ser de longitud 0 o de longitud 1. Los caracteres solo pueden ser de longitud 1. Puedes ver ejemplos aquí.

      Ayuda (consúltala si la necesitas, antes de ver la siguiente solución)

      Solución

   2. Un método

      string codificar(const string &) const;
      		

      que reciba una cadena de caracteres a codificar y devuelva, en forma de cadena de ceros y unos, el resultado de codificarla empleando el árbol de Huffman obtenido en el constructor. Se lanzará una excepción si el mensaje contiene algún carácter que no estaba en la tabla de caracteres y frecuencias inicial.

      Esta descripción de la Wikipedia, en su segunda lista numerada, te puede ayudar a saber lo que debes hacer para codificar un símbolo. Debes aplicar eso repetidamente, con cada carácter del mensaje a codificar.

      Ayuda con C++: método at de map

      Si intentas utilizar hojas[] en tu método codificar, verás que el compilador te dice que no puedes utilizar ahí un método que no es const. Lo puedes resolver utilizando hojas.at().

      Solución

   3. Un método

      string decodificar(const string &) const;
      		

      que reciba una cadena de ceros y unos resultante de una codificación previa (no hace falta comprobar que es así) y devuelva el resultado de decodificarla empleando el mismo árbol de Huffman.

      Esta descripción de la Wikipedia, en su tercera lista numerada, indica cómo decodificar un mensaje formado por un solo símbolo. Debes aplicar eso repetidamente, hasta decodificar el mensaje completo.

      Solución

   Prueba de la solución

   Recursos opcionales No es un objetivo de esta práctica obtener verdaderas secuencias de bits, nos conformamos con trabajar con cadenas de ceros y unos. Opcionalmente, si sientes curiosidad por cómo convertir esas cadenas en secuencias de bits, mira este ejemplo: BitsEmpaquetados.cpp. Otra posibilidad en C++, más simple, es emplear la clase bitset, por ejemplo: EjemploBitset.cpp.

2. 1. Clase de teoría TE1 17/10

      En el ejercicio 5 del tema 2 comparaste el coste temporal de cuatro implementaciones con estructuras de datos lineales para soportar las siguientes operaciones básicas del TAD Cola de Prioridad:

      • insertar
      • eliminarMínimo
      • consultarMínimo

      Añade ahora a ese estudio comparativo tres estructuras de datos más:

      5. un árbol binario de búsqueda
      6. un árbol AVL
      7. un montículo binario

      Solución

   2. El TAD Cola de Prioridad de Doble Fin, que se introdujo en la segunda semana de prácticas del tema 2 (ejercicio 6), se caracteriza por las siguientes operaciones básicas:

      • insertar
      • eliminarMínimo
      • consultarMínimo
      • eliminarMáximo
      • consultarMáximo

      Piensa cómo añadir las operaciones eliminarMáximo y consultarMáximo a cada una de las tres nuevas estructuras de datos del apartado a y cuál es el coste temporal en cada caso. ¿Cuál de esas tres soluciones elegirías para soportar las cinco operaciones?

      Solución

3. Analiza el coste temporal del siguiente algoritmo de ordenación con cada una de las 7 estructuras de datos consideradas en el ejercicio 2.a para implementar la cola de prioridad:

   void ordenar(vector<int> & v) {
   
      ColaDePrioridad cp;
   
      for (int dato : v)
         cp.insertar(dato);
   
      int i = 0;
      while (cp.talla() > 0) {
         v[i] = cp.consultarMínimo();
         i = i + 1;
         cp.eliminarMínimo();
      }
   }
   	    

   Solución

4. Utilizando la animación de un Min-Heap de David Galles, compara lo que sucede al insertar los enteros entre 31 y 1 en orden decreciente empleando la operación de inserción con lo que sucede al emplear (con su botón BuildHeap) el algoritmo de construcción de montículos en tiempo lineal, para ayudarte a entender la diferencia entre utilizar ese algoritmo y realizar n operaciones de inserción.

5. Clase de teoría TE1 17/10

   Analiza el coste temporal del siguiente algoritmo de ordenación si la clase ColaDePrioridad se implementa con un montículo binario y en el constructor de ColaDePrioridad se emplea el algoritmo de construcción de montículos binarios en tiempo lineal para inicializar el montículo con los datos que contiene el vector:

   void ordenar(vector<int> & v) {
   
      ColaDePrioridad cp(v);
   
      int i = 0;
      while (cp.talla() > 0) {
         v[i] = cp.consultarMínimo();
         i = i + 1;
         cp.eliminarMínimo();
      }
   }
   	    

   Solución

6. Clase de teoría TE1 17/10

   Para ver cómo funciona el algoritmo de ordenación Heapsort, utiliza la animación de Heapsort de David Galles, hasta entender lo que hace.

7. Supongamos que debes implementar una variante del TAD Cola de Prioridad que permita realizar las siguientes operaciones:

   void insertar(float);
   void eliminarMinimo();
   float consultarMinimo() const;
   void mezclar(const ColaDePrioridad &);
   	    

   El objetivo de la cuarta operación es mezclar dos colas de prioridad. Si cp1 y cp2 son dos colas de prioridad, tras ejecutar cp1.mezclar(cp2) la cola de prioridad cp1 debe contener todos los elementos que contenían previamente cp1 y cp2, mientras que cp2 no debe modificarse.

   Sabemos que las tres primeras operaciones se pueden realizar eficientemente si la estructura de datos empleada para representar internamente la cola de prioridad es un montículo binario. Explica cómo implementarías la cuarta operación con esa estructura de datos. Tu solución debe ser eficiente. Expresa en notación O el tiempo de ejecución en el peor caso de tu solución al mezclar dos colas de prioridad de talla n.

   Solución

8. ¿Cómo podemos cambiar (disminuir o aumentar) la prioridad de un elemento en un montículo binario si sabemos su posición, es decir, si no necesitamos buscarlo? ¿Cuál es el coste temporal en el mejor y en el peor caso de la operación?

   ¿Qué habría que hacer y cuál sería el coste temporal si no conociésemos la posición del dato y primero tuviésemos que buscarlo en el montículo?

   Solución

9. ¿Qué harías para que en una cola de prioridad, implementada con un montículo binario, se siga un orden FIFO al eliminar el mínimo cuando hay un empate entre elementos con la mínima prioridad?

   Solución

10. Dados dos montículos binarios, ambos de talla n, tienes que comprobar si contienen los mismos datos. Los puedes modificar. Explica cómo lo comprobarías, analiza el coste temporal en el mejor y en el peor caso de tu solución, e indica cuándo se dan ambos casos.

    Solución