Estructuras de Datos y Algoritmos - EDA (ETS de Ingeniería Informática).

Curso 2024-2025
Práctica 4. Implementación de la Cola de Prioridad de un Servidor
Hospitalario mediante un Montículo Binario

Departamento de Sistemas Informáticos y Computación. Universitat Politècnica de València

1. Objetivos
El principal objetivo de esta práctica es que el alumno aplique al diseño de una aplicación concreta los conceptos
sobre Cola de Prioridad y Montículo Binario que ha estudiado en el Tema 4 de la asignatura.
Específicamente, al concluir esta práctica el alumno deberá ser capaz de implementar la Cola de Prioridad
que usa una aplicación de Simulación de un Servidor de Planificación de Quirófanos eficiente, y ampliar la
aplicación con algunas funcionalidades adicionales.

2. Descripción del problema

Llamaremos Servidor de Planificación de Quirófanos (o, abreviadamente, Servidor de Quirófano) a una aplica-
ción que gestiona listas de espera de pacientes a los que sus médicos envían al hospital para alguna cirugía y
que, por tanto, están pendientes (a la espera) de ser operados en algún quirófano del hospital.
El modelo de gestión más sencillo que puede usar nuestro Servidor de Quirófano (o, en general, cualquier
servidor que tenga que asignar recursos limitados a un cierto conjunto de usuarios) es el FIFO (First In, First
Out), i.e. el modelo de una Cola. En la aplicación considerada, una Cola almacena, en orden de llegada, los
pacientes a operar, de forma que el primero de la Cola (First In) también es el primero que se elimina de esta,
porque va a ser operado (First Out), una vez un quirófano esté disponible.
Ahora bien, esta sencilla gestión FIFO presenta un problema para la salud de los pacientes si, por ejemplo,
hay muchos pacientes de poca gravedad que han sido diagnosticados antes (y han llegado antes al servidor)
que otros pacientes en estado más grave, y cuya cirugía sea mucho más urgente: estar en una lista de espera
gestionada mediante una cola FIFO podría agravar severamente su mal e incluso hacer innecesaria la cirugía,
¡podrían incluso morir mientras esperan! Afortunadamente, para reducir significativamente el tiempo medio de
espera de los pacientes más graves en el Servidor de Quirófano se puede hacer lo siguiente:
1. Asignar a los pacientes un indicador de su gravedad, i.e. de la urgencia de su cirugía, y usar este indicador
para gestionar su prioridad en la cola.
2. Gestionar los pacientes en espera de cirugía que almacena el Servidor de Quirófano con una Cola de
Prioridad implementada con un Montículo Binario.
Para comprobarlo, en esta práctica se completarán las implementaciones de simuladores con los dos tipos de
servidores descritos, que denominaremos Servidor Cola FIFO y Servidor Cola de Prioridad, y se compararán
los tiempos medios que esperan los pacientes de distinta gravedad para ser operados, en cada uno de ellos.

2.1. Las clases de una aplicación de simulación de un servidor de quirófano

Las principales clases que componen una aplicación de simulación de un servidor de quirófano son:
Paciente, que representa un paciente a operar. Un objeto de la clase Paciente tiene los siguientes atri-
butos:

• Un objeto Habitante (clase usada en la práctica 1) que lo identifica.

• Un String que especifica el tipo de cirugía.
• Un int, en el rango [0..9], que indica la gravedad del paciente. El valor menor, 0, corresponde a la
máxima gravedad y, por tanto, a la máxima prioridad en atención médica.

1
 • Dos int, que almacenan (en número de horas) los instantes en los que el paciente es diagnosticado
(entra en lista de espera) y es operado (entra en quirófano, sale de la lista de espera).

ServidorQuirofano interfaz que, modela un servidor de quirófano. Define las siguientes funcionalidades:
• insertarEnEspera(Paciente p), que añade un nuevo paciente p al servidor;
• hayPacientes(), que comprueba si quedan pacientes en el servidor;
• getPaciente(), que devuelve el paciente del servidor que va a ser operado;
• operarPaciente(int h), que elimina del servidor el paciente que va a ser operado y actualiza los
datos del paciente con el tiempo de su cirugía.
Además, en esta interfaz se define el tiempo de operación en quirófano que, por simplicidad, se ha fijado
en 3 horas para cualquier cirugía (TIEMPO_QUIROFANO).
ServidorColaFIFO, que representa un Servidor Cola FIFO. Clase que implementa ServidorQuirofano
y TIENE UNA Cola<Paciente> c como único atributo.
ServidorColaPrioridad, que representa un Servidor Cola de Prioridad. Clase que implementa la interfaz
ServidorQuirofano y TIENE UNA ColaPrioridad<Paciente> cP como único atributo.
SimuladorServidoresQuirofano, un programa Java que simula el funcionamiento de dos servidores de
quirófano, un Servidor Cola FIFO y un Servidor Cola de Prioridad, para calcular los tiempos medios que
esperan para ser operados los pacientes, según su gravedad. Los resultados experimentales determinarán
cuál de los dos servidores es el más adecuado en la atención hospitalaria.

También se proporcionan otras clases e interfaces (ServidorQuirofanoPlus, ServidorColaFIFOPlus,

SimuladorServidoresQuirofanoPlus). Se comentarán más adelante, al tratar la ampliación de la apli-
cación.

3. Actividades
Antes de llevar a cabo las actividades que se proponen en este apartado, es necesario que el alumno actualice
la estructura de paquetes y ficheros de su proyecto BlueJ eda.

eda

librerias aplicaciones

estructurasDeDatos util censo

 biblioteca
 pruebasOrdenacion

... ... ... ...
hospital
Paciente.java

modelos jerarquicos deDispersion

ServidorQuirofano.java



Cola.java MonticuloBinario.java . . .
   
ServidorQuirofanoPlus.java



ColaPrioridad.java lineales

ServidorColaFIFO.java


ArrayCola.java ServidorColaFIFOPlus.class


ServidorColaPrioridad.java




SimuladorServidoresQuirofano.class




SimuladorServidoresQuirofanoPlus.class



Para ello, hay que seguir estos pasos:

Abrir el paquete aplicaciones y crear en él un nuevo paquete de nombre hospital, que contendrá las clases
de la aplicación a desarrollar en esta práctica.

Abrir el paquete librerias.estructurasDeDatos y crear en él un nuevo paquete de nombre jerarquicos, que

contendrá la clase correspondiente al montículo binario.

2
 Salir de BlueJ seleccionando la opción Salir de la pestaña Proyecto.
Descargar los ficheros (.java) y (.class) disponibles en PoliformaT en sus correspondientes directorios,
tal y como muestra la figura anterior.
Entrar en el proyecto BlueJ eda y compilar las interfaces Cola y ColaPrioridad, situadas en el paquete
modelos, la clase ArrayCola, situada en el paquete lineales, y la clase MonticuloBinario, situada en el
paquete jerarquicos.
Salir de BlueJ seleccionando la opción Salir de la pestaña Proyecto.

3.1. Completar las clases Paciente y ServidorColaPrioridad

La clase Paciente debe implementar la interfaz Comparable para que sus objetos puedan incluirse en la EDA
ColaPrioridad. Para ello, se tiene que modificar la cabecera de la clase, y completar la implementación del
método compareTo atendiendo a los comentarios que se dan en la misma clase.
La clase ServidorColaPrioridad debe implementar correctamente la interfaz ServidorQuirofano. Así
pues, el alumno debe completar el constructor y los 4 métodos siguiendo las indicaciones dadas en el código de
esta clase.
La clase SimuladorServidoresQuirofano facilita los métodos testPaciente y testServidorQuirofano
que permiten verificar la implementación de las clases Paciente y ServidorColaPrioridad, respectivamente.

3.2. Ejecución de la aplicación SimuladorServidoresQuirofano

Si el código de las clases Paciente y ServidorColaPrioridad es correcto, al ejecutar el programa main de la
clase SimuladorServidoresQuirofano, se mostrará en la terminal los resultados de una simulación que permite
comparar los tiempos medios que esperan para ser operados los pacientes según su gravedad, en un Servidor
Cola y en un Servidor Cola de Prioridad.
La ejecución de este método main puede hacerse de dos formas:
Sin argumentos. En tal caso, el programa usa sus valores por defecto: 100 pacientes y modo verbose
desactivado.
Especificando dos argumentos. El primero debe ser el número de pacientes a incluir en la lista de espera de
los servidores. El segundo, con posibles valores ("SI", "NO"), especifica si se activa, o no, el modo verbose.
El programa, en cualquier caso, genera una secuencia aleatoria de pacientes, y con la misma secuencia se
construyen la cola FIFO y la cola de prioridad de los dos tipos de servidores. A continuación, el programa realiza
la simulación con ambos servidores. Si el modo verbose está desactivado, solamente se muestran los tiempos de
espera medios. En cambio, si se activa verbose, se muestra además la información detallada de cada paciente en
la simulación. Para acotar la salida en la terminal, no se recomiendan ejecuciones con más de 50 pacientes en
lista de espera y modo verbose activo.
Se sugiere realizar las siguientes simulaciones:
Sin argumentos.
Con argumentos: "50", "SI".
Con argumentos: "200", "NO".

Con argumentos: "1000", "NO".

La lectura de los resultados establecerá claramente la idoneidad del uso de la cola de prioridad en esta apli-
cación hospitalaria (o, dicho de otra manera, lo poco recomendable que resulta la gestión FIFO de los recursos
del hospital).
NOTA. Cada vez que se ejecuta el programa SimuladorServidoresQuirofano se genera de forma aleatoria
un conjunto de pacientes y, por tanto, los resultados que aparece en la terminal son siempre distintos de los
anteriores, incluso especificando los mismos argumentos.

3
3.3. Descripción de las nuevas funcionalidades a incorporar
La aplicación desarrollada usa solamente un quirófano para atender a los pacientes en lista de espera. Lógicamen-
te, si se especifica un número muy elevado de pacientes a operar, los tiempos de espera pueden ser inaceptables,
se use el servidor que se use.
Por ello, ampliaremos la aplicación de modo que si el número de pacientes supera un umbral dado, entonces
se abra un nuevo quirófano, y a partir de ese momento dos quirófanos atiendan, en paralelo, a los pacientes.
Los nuevos servidores, llamados ServidorColaFIFOPlus y ServidorColaPrioridadPlus, serán clases que
implementen un nuevo interfaz, ServidorQuirofanoPlus, que extiende el anterior ServidorQuirofano. Para
las nuevas simulaciones se usará el programa SimuladorServidoresQuirofanoPlus.
La subinterfaz ServidorQuirofanoPlus define los siguientes métodos:
numPacientes(), que devuelve el número de pacientes en el servidor;

transferirPaciente(), que “transfiere“ un paciente, en concreto, lo elimina de un servidor, y lo devuelve

para, después, insertarlo en otro servidor (esto último no lo hará este método);
distribuirPacientes(ServidorQuirofanoPlus s), que “distribuye“ todos los pacientes de un servidor
entre dos servidores de forma equitativa.

3.4. Implementar la clase ServidorColaPrioridadPlus

La clase ServidorColaFIFOPlus se proporciona completa. y compilada. El alumno debe implementar la clase
ServidorColaPrioridadPlus teniendo en cuenta las siguientes indicaciones:
La clase extenderá ServidorColaPrioridad e implementará ServidorQuirofanoPlus.

La clase tendrá un atributo privado entero que representará la talla de la cola de prioridad.
El método numPacientes() simplemente devolverá el valor de ese nuevo atributo, talla.
El método transferirPaciente() devolverá el paciente más prioritario de la cola, de donde será borrado
(lo que implica modificar adecuadamente el atributo talla).

El método distribuirPacientes(ServidorQuirofanoPlus s) recibirá un servidor s nuevo, vacío, sin

pacientes. El método repartirá los pacientes de this entre this y s del siguiente modo:
• Se crea un array de pacientes cuyo tamaño sea la talla de this.
• Mediante un bucle, se “transfieren“ al array todos los pacientes de this, en orden de prioridad (PISTA:
usar el método transferirPaciente).
• Mediante otro bucle, se insertan los pacientes transferidos al array, alternadamente, a los dos servi-
dores this y s. Dicho de otra forma, los pacientes en posiciones pares del array se insertan en un
servidor, y los pacientes en posiciones impares del array se insertan en el otro servidor. De esta forma,
se valora la gravedad de los pacientes para repartirlos equitativamente entre los dos servidores.

Además, los métodos insertarEnEspera y operarPaciente deben sobreescribirse para actualizar ade-
cuadamente el atributo talla en esas operaciones. (IMPORTANTE: aplicar correctamente la herencia,
invocando con super los métodos homónimos de la superclase).
La clase SimuladorServidoresQuirofanoPlus facilita el método testServidorQuirofanoPlus que permite
verificar la implementación de ServidorColaPrioridadPlus.

3.5. Ejecución de la aplicación SimuladorServidoresQuirofanoPlus

Al ejecutar el programa mainPlus de la clase SimuladorServidoresQuirofanoPlus, se mostrará en la terminal
los resultados de una simulación que permite comparar los tiempos medios que esperan para ser operados los
pacientes según su gravedad, en los servidores ampliados mediante las clases ServidorColaFIFOPlus y en un
ServidorColaPrioridadPlus, así como también los otros dos servidores anteriores.
Se sugiere realizar las simulaciones para 300, 1000, y 5000 pacientes. La lectura de los resultados debiera
confirmar las ventajas de la cola de prioridad, frente a la cola FIFO, en la gestión hospitalaria, con independencia
de los recursos disponibles para atender a los pacientes.