PRÁCTICA Nš 8: 1 sesión (Opcional)
(del 2 al 6 de Junio de 2003)
Implementación de la Clase maxHeap
(montículo de máximos)
0. Objetivos
En esta práctica nos limitaremos a escribir la clase Heap (de máximos), y la utilizaremos en un programa de ejemplo proporcionado por el profesor.
1. Introducción
|
Un heap de máximos, max heap, es un árbol binario completo tal que, el valor de la clave de cada nodo es mayor o igual que las claves de sus nodos hijos (si los tiene). Además sus hijos cumplen la propiedad de heap de máximos De la definición se deduce que la clave contenida en el nodo raíz de un max heap (min heap) es la mayor clave del árbol. Pero esto no quiere decir que sea la única con ese valor. |
Montículo de máximos |
La estructura heap 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áxima (o mínima) prioridad.
Los heaps, como árboles binarios completos que son, se pueden representar de forma eficaz mediante una estructura secuencial (un array).
2. Especificación del interfaz de la clase
La interfaz de la clase será la siguiente:
class Heap
{
public:
Heap (void);
bool Insertar (Valor);
bool EliminarMaximo (void);
bool ConsultarMaximo (Valor &);
bool HeapVacio (void);
private:
Vector info;
int num;
};
donde el tipo vector se define como:
typedef Valor Vector [MAX];
y el tipo valor y el máximo son:
typedef string Valor;
const int MAX = 1000;
3. Realización de la práctica
Én esta práctica se escribirán los ficheros necesarios para implementar la clase y se utilizará esta clase en un programa de prueba que proporcionará el profesor.
Este programa utiliza la estructura del heap para ordenar ficheros compuestos por palabras (animales.txt, fichero.txt).
La salida del programa se muestra por pantalla y consiste en la secuencia de palabras tal y como ha sido leida del fichero y posteriormente la misma secuencia ordenada.
4. Trabajo adicional
Se propone como tarea adicional la posibilidad de implementar los montículos de forma dinámica (aunque no es la forma adecuada, ni habitual de implementar montículos).
4. Entrega de Programas
Antes del día 16 de Junio a las 20:00 se entregarán al profesor los dos ficheros relativos a la clase:
Ficheros de la clase maxHeap (##maxHeap.cpp y ##maxHeap.h)
Nota Muy Importante
Antes de poder empezar a realizar cualquiera de las prácticas es necesario presentar las hojas de especificación de programas (documentación de programas) con las tareas que se van a realizar en la práctica, explicando brevemente como se van a solucionarse los problemas que se plantean.
ENTREGA DE PROGRAMAS:
Antes del Lunes 16 de Junio a las 20:00 horas