Priority Queue para objetos

Supón que necesitas crear un priority queue de objetos de clase Patient.

class Patient {
private:
  int age;
  string lastName;
public:
  Patient(int a, string ln) : age(a), lastName(ln) {}
};

Los algoritmos de inserción, búsqueda y remoción en estructuras como el binary search tree y el heap requieren poder comparar los elementos que estamos guardando. En el STL por default se usa el operator< (menor que) para comparar los elementos en un heap y otros contenedores. Así que para poder crear un priority queue de objetos Patient debemos sobrecargar el operator< de esa clase, e.g. establecer bajo que condiciones un objeto Patient A es menor que el objeto Patient B.

Digamos que queremos establecer que A < B si la edad de A es menor que la de B o si las edades son iguales y el apellido de A es lexicográficamente menor que B.

Por ejemplo, en este caso A es menor que B.

Patient A(5, "Govinda");
Patient B(6, "Baez");

En este caso C no es menor que D.

Patient C(15, "Roma");
Patient D(15, "Castro");

Ejercicio: En el siguiente código inserta la implementación de operator<para la clase Patient. Al hacerlo correctamente las instrucciones de comparación que aparecen en la función mainmostrarán los resultados de las comparaciones que acabamos discutir.

Max priority queue

Habiendo implementado operator< podemos crear un priority queue de objetos de clase Patient. Nota que el priority queue asigna mayor prioridad a los objetos mayores. Por eso al retirarlos los obtenemos en orden de mayor a menor edad. Correr el siguiente programa para que veas..

Min priority queue

¿Qué hacer si necesitamos un min priority queue en vez de un max priority queue? Podemos redefinir el operator< para que actue al revés, i.e. en vez de dar cierto cuando la edad de A es menor que la de B, dar cierto cuando la edad de A es mayor que la de B. En el código a continuación observa cómo hemos cambiado la implementación de operator<. Corre el programa para que veas el efecto que tuvo ese cambio.

Ejercicio

Supón que deseamos simular el orden en que son atendidos los pacientes que llegan a un consultorio. Tu programa leerá un listado de llegadas (una llegada por linea). Cada llegada consiste de tres campos: 1. el horario de llegada (expresado en minutos desde que abre el consultorio) 2. la edad del paciente 3. el apellido del paciente

Mientras haya pacientes en sala y el doctor no esté ocupado se atiende al paciente con menor edad que esté en sala. Atender a cada paciente toma 15 minutos.

Por ejemplo, si el orden de llegada es:

10 8 Melendez
20 10 Garcia
23 4 Colon
30 12 Serrano
44 1 Rios
100 4 Rovira

El doctor atiende a Melendez en el minuto 10. En el minuto 25 termina con Melendez tiene a Garcia y Colon en sala. Escoge a Colon por ser más joven. Cuando termina con Colon en el minuto 40 tiene a Garcia y Serrano. Atiende a Garcia y así.

El output del programa sería así:

minuto 10: atiende a Melendez
minuto 25: atiende a Colon
minuto 40: atiende a Garcia
minuto 55: atiende a Rios
minuto 70: atiende a Serrano
minuto 100: atiende a Rovira