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:
En este sentido, existen dos tipos de colas de prioridad:
- Cola de prioridad ascendente.
- 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 en base al menor de los elementos almacenados en ella. Para que ésto 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í.
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)).
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 en la siguiente figura:
 |
| 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 un objeto de la clase Integer o de la clase Float por ejemplo, la comparación es posible pero, ¿qué ocurre con objetos de la clase String del API de Java, o con las clases Persona y Cientifico definidas en la entrada POO (herencia) por ejemplo?
Implementación.
En la orientación a objetos existe un concepto relacionado con la herencia: la herencia múltiple. La herencia múltiple básicamente es la capacidad de una clase de heredar los atributos y métodos de más de una clase; sin embargo, el lenguaje de programación Java no incluye en su gramática dicha capacidad, aunque por otro lado, incorpora un mecanismo que permite que una clase se comprometa, a través de una especie de contrato, a implementar en métodos las operaciones declaradas o establecidas en una interfaz (interface). La interfaz Comparable del API de Java compromete u obliga a las clases que la implementan, a establecer una relación de orden entre los objetos que la implementen. Dicha relación de orden es arbitraria y está en función únicamente del interés o de las necesidades específicas de la clase en cuestión.
Para ilustrar lo anterior, considere el Ejemplo ColaAscendente 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. Note el uso de la interfaz Comparable. Observe con detenimiento la línea 6 la cual, en el contexto de lo anterior, podría interpretarse de la siguiente manera:
Para ilustrar lo anterior, considere el Ejemplo ColaAscendente 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. Note el uso de la interfaz Comparable. Observe con detenimiento la línea 6 la cual, en el contexto de lo anterior, podría interpretarse de la siguiente manera:
La clase ColaAscendente es una subclase, clase hija o clase derivada de la clase Cola, gestiona objetos genéricos T que definan o establezcan una relación de orden a través de la implementación del método compareTo declarado en la interfaz Comparable.
Observe que el mensaje o la invocación del método compareTo ocurre en la línea 21 del Ejemplo ColaAscendente, y que la idea general del método inserta (líneas 15-35) consiste en recorrer la secuencia de nodos (líneas 21-24) mientras haya nodos por procesar y no se haya encontrado el lugar correspondiente para el elemento a insertar (línea 21). En este sentido, el método compareTo compara el objeto receptor del mensaje con el objeto proporcionado como argumento; dicho método regresa uno de tres posibles valores (consulte en el API de Java la interfaz Comparable para ampliar y complementar la información al respecto):
- Un entero negativo (< 0) si el objeto receptor del mensaje es menor que el objeto proporcionado como argumento.
- Cero (0) si el objeto que recibe el mensaje es igual al objeto proporcionado como argumento.
- Un entero positivo (> 0) si el objeto receptor del mensaje es mayor que el objeto proporcionado como argumento.
Es importante que el lector comprenda que el método compareTo es definido en la clase que quiera establecer una relación de orden para sus objetos, es decir, los objetos de la clase genérica T deberán tener la definición (código) de dicho método.
Continuando con la explicación del método inserta del Ejemplo ColaAscendente, note que el método hace uso de objetos auxiliares (líneas 16, 18 y 19), para poder realizar el ajuste de las referencias correspondientes en las líneas 26-34. Aquí cabe mencionar que, aunque dichos objetos pudieron haber sido definidos como atributos de la clase ColaAscendente, 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 22-23 y 26-34 se dejan como ejercicio para el lector, a quien se insta amablemente a comprender completamente su funcionamiento antes de continuar.
Continuando con la explicación del método inserta del Ejemplo ColaAscendente, note que el método hace uso de objetos auxiliares (líneas 16, 18 y 19), para poder realizar el ajuste de las referencias correspondientes en las líneas 26-34. Aquí cabe mencionar que, aunque dichos objetos pudieron haber sido definidos como atributos de la clase ColaAscendente, 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 22-23 y 26-34 se dejan como ejercicio para el lector, a quien se insta amablemente a comprender completamente su funcionamiento antes de continuar.
Por último, la clase de prueba para la cola de prioridad ascendente del Ejemplo ColaAscendente se muestra en el Ejemplo PruebaColaAscendente.
Tómese el lector el tiempo que considere necesario para comparar el Ejemplo PruebaColaAscendente con el Ejemplo PruebaCola y advierta que son, esencialmente iguales.
Note también que los objetos a almacenar en la cola de prioridad ascendente son objetos de la clase Integer (línea 6) por lo que, para que no haya ningún problema en la compilación, dicha clase deberá tener la implementación (implements) de la interfaz Comparable, y en consecuencia, la definición del método compareTo. En este sentido, se invita al lector para que realice dicha comprobación en el API de Java antes de compilar y ejecutar el Ejemplo PruebaColaAscendente.
Tómese el lector el tiempo que considere necesario para comparar el Ejemplo PruebaColaAscendente con el Ejemplo PruebaCola y advierta que son, esencialmente iguales.
Note también que los objetos a almacenar en la cola de prioridad ascendente son objetos de la clase Integer (línea 6) por lo que, para que no haya ningún problema en la compilación, dicha clase deberá tener la implementación (implements) de la interfaz Comparable, y en consecuencia, la definición del método compareTo. En este sentido, se invita al lector para que realice dicha comprobación en el API de Java antes de compilar y ejecutar el Ejemplo PruebaColaAscendente.
Con base en lo anterior, todos los objetos que se deseen almacenar en la cola de prioridad ascendente definida en el Ejemplo ColaAscendente, deberán implementar dicha interfaz, así como definir el comportamiento requerido (código) por el método compareTo.
Por último, observe que a diferencia del Ejemplo PruebaCola, el Ejemplo PruebaColaAscendente inserta intencionalmente nueve números de manera desordenada, ya que la implementación de cola de prioridad propuesta (Ejemplo ColaAscendente) los mantiene ordenados dentro de la estructura de datos, mientras que la eliminación (líneas 18-26) se realiza de manera convencional. La salida del Ejemplo PruebaColaAscendente se muestra en la siguiente figura:
Por último, observe que a diferencia del Ejemplo PruebaCola, el Ejemplo PruebaColaAscendente inserta intencionalmente nueve números de manera desordenada, ya que la implementación de cola de prioridad propuesta (Ejemplo ColaAscendente) los mantiene ordenados dentro de la estructura de datos, mientras que la eliminación (líneas 18-26) se realiza de manera convencional. La salida del Ejemplo PruebaColaAscendente se muestra en la siguiente figura:
 |
| Salida del Ejemplo PruebaColaAscendente. |
Cola de prioridad descendente.
La cola de prioridad descendente es análoga en lo general a la cola de prioridad ascendente.
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 en base al mayor de los elementos almacenados en ella. Al igual que para la cola de prioridad ascendente, para que ésto ú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.
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 en base al mayor de los elementos almacenados en ella. Al igual que para la cola de prioridad ascendente, para que ésto ú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.
