Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

4. Colas de prioridad mediante montículos

Horas de clases presenciales: 4 (2 teoría + 2 prácticas)
Horas de trabajo no presencial: 6
Ratio: 3 horas no presenciales por cada clase de 2 horas

Recursos

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:

También utilizaremos la animación de un Min-Heap y la animación de Heapsort de David Galles o la animación Binary Heap + Priority Queue de Jakub Melezinek.

Adelantaremos la presentación del algoritmo de Huffman, que forma parte del tema 5, para poder trabajar con él en clase de prácticas. En el mismo libro, aparece en el siguiente apartado del capítulo 10 "Algorithm Design Techniques":

Recursos en castellano y opcionales

Si no te gusta el libro recomendado arriba o necesitas un texto en castellano, puedes recurrir a los siguientes textos alternativos para entender este tema:

  • Los siguientes apartados del libro "Estructuras de datos en Java" (2013) de M. A. Weiss:

    • 6 La API de Colecciones
      • 6.9 Colas con prioridad
    • 12 Utilidades
      • 12.1 Compresión de archivos
        • 12.1.1 Códigos prefijo
        • 12.1.2 Algoritmo de Huffman
    • 21 Una cola con prioridad: el montículo binario
      • 21.1 Ideas básicas
        • 21.1.1 Propiedad estructural
        • 21.1.2 Propiedad de ordenación del montículo
        • 21.1.3 Operaciones permitidas
      • 21.2 Implementación de las operaciones básicas
        • 21.2.1 Inserción
        • 21.2.2 La operación deleteMin
      • 21.3 La operación buildHeap: construcción de un montículo en tiempo lineal
      • 21.4 Operaciones avanzadas: decreaseKey y merge
      • 21.5 Ordenación interna: heapsort
  • Los siguientes apartados del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff:

    • 13 Ordenación
      • 13.2 Montículos, ordenación con montículo y colas de prioridad
    • 15 Árboles
      • 15.1 Caso de estudio: códigos de Huffman

También te puede interesar esto.

De las transparencias que acompañan al libro "Algorithm Design" de Jon Kleinberg y Éva Tardos preparadas por Kevin Wayne te pueden interesar estas:

  • Binary heap demo

  • 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")

Ejercicios

  1. Clase de teoría TE1 14/10, TE2 19/10
    Clase de prácticas LA1 y LA3 21/10, LA2 y LA4 26/10

    Este es un ejercicio práctico sobre el algoritmo de Huffman, explicado previamente en clase de teoría 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).

    Ayuda con C++

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

    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.

    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 funcione este ejemplo de uso TestHuffman.cpp y produzca una salida análoga a esta TestHuffman.salida (no necesariamente la misma). 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. El constructor, aplicando el algoritmo de Huffman, debe construir el árbol de Huffman, contando con 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 a continuación: en uno de ellos entraremos por las hojas y nos moveremos hacia el padre hasta la raíz, y en otro entraremos por la raíz y nos moveremos hacia los hijos hasta una hoja.

      Esta descripción de la Wikipedia, en su primera lista numerada, te puede ayudar a recordar lo que debes hacer.

      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 carácteres y frecuencias inicial.

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

      Ayuda con C++ Si intentas utilizar hojas[] en ese método, 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

    Código de prueba

    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.

    1. Clase de teoría TE2 26/10

      En el ejercicio 6 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:

      1. un árbol binario de búsqueda
      2. un árbol AVL
      3. 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 3), 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

  2. Clase de teoría TE2 26/10, TE1 28/10

    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

  3. 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 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.

  4. Clase de teoría TE2 26/10, TE1 28/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

  5. 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

  6. Hemos presentado un algoritmo que permite construir un montículo en tiempo O(n) a partir de n datos iniciales dados. El algoritmo no consiste en hacer n operaciones de inserción, lo cual costaría O(n log n), sino en hacer algo diferente.

    ¿Sería posible diseñar un algoritmo que, análogamente, a partir de n datos iniciales cualesquiera, construyese en tiempo O(n) un árbol binario de búsqueda o un árbol AVL de talla n con un dato en cada nodo?

    Ayuda

    Solución

  7. Clase de teoría TE2 26/10

    ¿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

  8. ¿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

  9. Clase de teoría TE2 26/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

  10. Clase de teoría TE2 26/10, TE1 28/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.

Opcionalmente, en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de este tema si quieres seguir practicando.