Colas de prioridad (C++).

   La cola de prioridad es una estructura de datos en la que el ordenamiento intrínseco de los elementos determina el resultado de la aplicación de sus operaciones básicas o primitivas.

   En este sentido, existen dos tipos de colas de prioridad:

1. Cola de prioridad ascendente.
2. Cola de prioridad descendente.

   Ambas estructuras de datos redefinen la forma de operación convencional respecto de una cola de espera, por lo que serán estudiadas de manera separada.

Cola de prioridad ascendente.

   La cola de prioridad ascendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza de manera convencional, pero la eliminación se realiza con base en el menor de los elementos almacenados en ella. Para que esto sea posible, los elementos que almacena la estructura de datos deben tener una relación de orden; es decir, deben poseer algún mecanismo que permita compararlos entre sí para saber si dados dos elementos, uno es menor, mayor o igual que el otro.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad ascendente con la redefinición o sobre escritura (override) del método elimina. Observe cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones previamente existentes se conservan (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)).

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método elimina.

    Otro tipo de representación para la cola de prioridad ascendente, consiste en mantener ordenados los elementos de manera ascendente durante la inserción y conservar la operación de eliminación de la forma convencional. Dicha representación se expresa en UML como se muestra a continuación:

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método inserta.

    En resumen, en una cola de prioridad ascendente los elementos se recuperan (eliminan) en orden ascendente respecto de la relación de orden que guarden entre sí. Ahora bien, para objetos con una relación de orden inherente a ellos, como int o  string por ejemplo la comparación es posible pero, ¿qué ocurre con objetos de las clases persona y cientifico definidas en la entrada POO (herencia) por ejemplo? Por ahora se invita al lector a reflexionar para que en la sección de ejercicios lo pueda solucionar.

   Implementación.

   Considere el Ejemplo cola_ascendente el cual implementa una cola de prioridad ascendente sobre escribiendo o redefiniendo (override) el método inserta tal y como se propone en el diagrama de clases UML de la figura anterior. Observe con detenimiento la línea 59 la cual, en el contexto de lo anterior, podría interpretarse de la siguiente manera:

La clase cola_ascendente es una subclase, clase hija o clase derivada de la clase cola, gestiona objetos genéricos de tipo T que definan o establezcan una relación de orden a través del operador mayor qué (>).

   Observe que el mensaje o la invocación del operador > ocurre en la línea 203 del Ejemplo cola_ascendente, y que la idea general del método inserta (líneas 197-217) consiste en recorrer la secuencia de nodos (líneas 203-206) mientras haya nodos por procesar y no se haya encontrado el lugar correspondiente para el elemento a insertar (línea 203). Es importante que el lector comprenda que el operador > deberá ser implementado para los objetos o elementos de tipo T que se deseen almacenar en la cola de prioridad.

   Continuando con la explicación del método inserta del Ejemplo cola_ascendente, note que el método hace uso de objetos auxiliares (líneas 199-201), para poder realizar el ajuste de las referencias correspondientes en las líneas 208-216. Aquí cabe mencionar que, aunque dichos objetos pudieron haber sido definidos como atributos de la clase cola_ascendente, en realidad no representan una característica o cualidad inherente a los objetos que se deriven de dicha clase, sino que más bien son entidades útiles para la manipulación de la estructura de datos dentro del método, por lo que de ser atributos, aunque la implementación trabajaría de la misma manera, el enfoque sería inapropiado, esto es: sería un diseño inadecuado. El análisis y los detalles del ajuste de las referencias de las líneas citadas se dejan como ejercicio para el lector, a quien se insta amablemente a comprender completamente su funcionamiento antes de continuar.

 

   Tómese el lector el tiempo que considere necesario para comparar el Ejemplo cola_ascendente con el Ejemplo cola y advierta que son, esencialmente iguales. En este sentido y como ayuda en su comparación, note que en la línea 64 se ha especificado que el método inserta sobrescribe (override) el comportamiento definido en la súper clase.

    Note también que los objetos a almacenar en la cola de prioridad ascendente son objetos de la clase string (línea 223) por lo que, para que no haya ningún problema en la compilación, dicha clase deberá tener la implementación del operador correspondiente como se ha mencionado con anterioridad.

   Por último, observe que a diferencia del Ejemplo cola, el Ejemplo cola_ascendente inserta intencionalmente nueve números de manera desordenada (líneas 225-233), ya que la implementación de la cola de prioridad en cuestión los mantiene ordenados dentro de la estructura de datos, mientras que la eliminación (líneas 236-246) se realiza de manera convencional. La salida del ejemplo se muestra a continuación:

La Cola de prioridad ascendente es: 1
La Cola de prioridad ascendente es: 1 8
La Cola de prioridad ascendente es: 1 3 8
La Cola de prioridad ascendente es: 1 3 6 8
La Cola de prioridad ascendente es: 1 3 5 6 8
La Cola de prioridad ascendente es: 1 3 4 5 6 8
La Cola de prioridad ascendente es: 1 3 4 5 6 7 8
La Cola de prioridad ascendente es: 1 2 3 4 5 6 7 8
La Cola de prioridad ascendente es: 1 2 3 4 5 6 7 8 9

Elemento eliminado de la cola: 1
La Cola de prioridad ascendente es: 2 3 4 5 6 7 8 9
Elemento eliminado de la cola: 2
La Cola de prioridad ascendente es: 3 4 5 6 7 8 9
Elemento eliminado de la cola: 3
La Cola de prioridad ascendente es: 4 5 6 7 8 9
Elemento eliminado de la cola: 4
La Cola de prioridad ascendente es: 5 6 7 8 9
Elemento eliminado de la cola: 5
La Cola de prioridad ascendente es: 6 7 8 9
Elemento eliminado de la cola: 6
La Cola de prioridad ascendente es: 7 8 9
Elemento eliminado de la cola: 7
La Cola de prioridad ascendente es: 8 9
Elemento eliminado de la cola: 8
La Cola de prioridad ascendente es: 9
Elemento eliminado de la cola: 9
Vacia: Cola de prioridad ascendente

 

Cola de prioridad descendente.

   La cola de prioridad descendente es análoga en lo general a la cola de prioridad ascendente, por lo que a continuación sólo se harán las consideraciones pertinentes.

   La cola de prioridad descendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza también de la manera convencional, pero la eliminación se realiza con base en el mayor de los elementos almacenados en ella. Al igual que para la cola de prioridad ascendente, para que esto último sea posible es necesario que los elementos que almacena la estructura de datos tengan una relación de orden, es decir, es preciso que incorporen algún mecanismo que les permita compararlos entre sí.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad descendente con la redefinición o sobre escritura (override) del método elimina. Una vez más, note cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)) previamente existentes se conservan.

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método elimina.

    Al igual que para la cola de prioridad ascendente, otro tipo de representación para la cola de prioridad descendente consiste en mantener ordenados los elementos de manera descendente durante la inserción y conservar la operación de eliminación de la forma convencional tal y como lo sugiere la representación del diagrama de clases UML de la siguiente figura:

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método inserta.

    Por último, recuerde que en una cola de prioridad descendente los elementos se recuperan (eliminan) en orden descendente respecto de la relación de orden que guardan entre sí. Los detalles de la implementación, se dejan como ejercicio para el lector.