Esta práctica tiene dos objetivos:

• La manipulación de árboles binarios representados mediante vectores.
• La utilización de montículos (heaps) como colas de prioridad.

Un montículo de mínimos, min heap, es un árbol binario completo tal que, el valor de la clave de cada nodo es menor o igual que las claves de sus nodos hijos (si los tiene). Además, sus hijos cumplen la propiedad de montículo de mínimos.

De la definición se deduce que la clave contenida en el nodo raíz de un min heap es la menor clave del árbol. Pero esto no quiere decir que sea la única con ese valor.

La estructura montículo tiene interesantes aplicaciones, por ejemplo, la ordenación de arrays (algoritmo heapsort) o el mantenimiento de las llamadas colas de prioridad. Las colas de prioridad son un tipo especial de colas donde todo elemento que se inserta en la cola lleva asociado una prioridad, de forma que el elemento que se borra de la cola es el primero entre los que tengan la mínima (o máxima) prioridad.

Los montículos, como árboles binarios completos que son, se pueden representar de forma eficaz mediante una estructura secuencial (un array). La interfaz de la clase será la siguiente:

Como ejemplo de utilización de la clase Monticulo, se propone plantear la simulación del funcionamiento de un ascensor:

Una empresa instaladora de ascensores, nos encarga diseñar el sistema de control para sus ascensores. De forma que, podamos instalarlos en cualquier edificio con tal de indicar, al principio, el número de plantas de las que consta dicho edificio (incluyendo la planta baja) y con un máximo de 64 plantas.

La filosofía de funcionamiento del ascensor es la siguiente:

1. Todas las peticiones realizadas por los usuarios son tratadas de igual forma, no importa que se trate de llamadas internas o externas (al ascensor).
2. Para que el movimiento del ascensor se realice de manera eficiente, las llamadas se priorizarán y serán atendidas en función de la prioridad asociada. Este valor dependerá fundamentalmente de la posición actual del ascensor y del sentido de la marcha. En concreto, el algoritmo para asignar valores de prioridad a las llamadas es el siguiente:

Como la medida de prioridad utilizada está relacionada con lo cerca que está el piso de la posición actual, se interpreta como mejor prioridad el valor de prioridad mínimo.

Con este planteamiento, hay que escribir un programa que simule el funcionamiento del ascensor de forma que las peticiones se realicen mediante pulsaciones del teclado y después se mueva el ascensor a los pisos que se han solicitando previamente.

Para gestionar las llamadas solicitadas y la prioridad asignada a cada una de ellas, es preciso mantener 2 colas de prioridad (montículos de mínimos). Una de las colas almacenará las peticiones que se pueden atender siguiendo el sentido actual de la marcha y la otra cola guardará las peticiones que requieren que se cambie el sentido de la marcha del ascensor para ser atendidas.

Hay que tener en cuenta que, antes de visualizar el movimiento del ascensor, recogeremos todas las peticiones de pisos en los que queremos parar. Una vez terminado todo el recorrido, daremos la opción de volver a introducir nuevas peticiones. Para ello se propone que, mientras no se introduzca el carácter ‘$’ se supone que son peticiones realizadas en el mismo momento y que se visualizarán en conjunto. Utilizaremos el carácter ‘-‘ cuando deseemos salir del programa.

Las llamadas se simularán con pulsaciones de teclas de la siguiente manera: Teclas '0'..'9' indican pisos del 0 al 9, teclas 'A'..'Z' indican pisos del 10 al 36 (incluir 'Ñ' que debe corresponder con el piso 24) y teclas 'a'..'z' indican pisos del 37 al 63 (incluir 'ñ' que corresponde con el piso 51). Por tanto, habrá que realizar una función que convierta estos caracteres a los números de piso correspondientes para poder utilizar la función de visualización del movimiento del ascensor.

La visualización del proceso se realizará utilizando la clase proporcionada por el profesor, llamada Ascensor.cpp y que contiene dos métodos básicos (se recomienda consultar el resto de los métodos en el propio archivo fuente):

El esquema algorítmico básico de la simulación será el siguiente:

Hay que tener en cuenta que los montículos almacenan básicamente el valor del piso desde donde se realiza la llamada pero con signo positivo o negativo, dependiendo del sentido de la marcha. Esto quiere decir que a la hora de extraer valores de los montículos para mover el ascensor, habrá que considerar el valor absoluto de las prioridades, puesto que no hay pisos negativos.

Nota: Se debe incluir en el proyecto, además de la clase ascensor, el fichero "conio.c" proporcionados por el profesor.

La entrega de esta práctica debe incluir el código con el programa principal y las funciones del programa que implemente el funcionamiento del ascensor (##movimiento.cpp) que contendrá básicamente el esquema algorítmico antes mencionado, y la implementación de la clase ‘Monticulo’ (##monticulo.cpp y ##monticulo.h).