Estructuras de Datos: Cola de prioridades

Una Cola  -en el contexto de las Ciencias de la Computación- es una estructura de datos FIFO. Esto significa que los primeros elementos que fueron ingresados en la cola serán primeros en ser removidos. Además, los nuevos elementos a ingresar a lo cola serán colocados en la parte posterior de la misma, como los clientes en las colas de los Bancos.

Eso lo sé desde la Universidad.

Sin embargo, en Data Structures and Algorithms in Java  descubrí un tipo de Cola llamada Colas de Prioridades; donde los elementos la posición de los elementos en la Cola está en función a un criterio predefinido; como en las colas de las discotecas en las que las jovencitas agraciadas siempre ingresan primero, sin importar la hora en la que hallan llegado.

Les presento el código que incluye el libro, para una Cola de Prioridades donde se procura que los elementos de menor valor numérico -nuestro criterio-sean removidos primero de la cola:

 package cgc.learning;  
 public class PriorityQ {  
      private int maxSize;  
      private long[] queArray;  
      private int nItems;  
      public PriorityQ(int s) {  
           maxSize = s;  
           queArray = new long[maxSize];  
           nItems = 0;  
      }  
      public void insert(long item) {  
           int j;  
           if (nItems == 0) {  
                queArray[nItems++] = item;  
           } else {  
                for (j = nItems - 1; j >= 0; j--) {  
                     if (item > queArray[j]) {  
                          queArray[j + 1] = queArray[j];  
                     } else {  
                          break;  
                     }  
                }  
                queArray[j + 1] = item;  
                nItems++;  
           }  
      }  
      public long remove() {  
           return queArray[--nItems];  
      }  
      public long peekMin() {  
           return queArray[nItems - 1];  
      }  
      public boolean isEmpty() {  
           return (nItems == 0);  
      }  
      public boolean isFull() {  
           return (nItems == maxSize);  
      }  
 }  

Nuestra Cola de prioridades está implementada en la clase PriorityQ, que para inicializarse requiere como parámetro el máximo número de elementos que puede soportar la cola. Usaremos este número para instanciar el arreglo de longs que contendrá la data.

Iremos agregando data en el arreglo mediante el método insert, que es también el encargado de que los elementos sean insertados en orden. Se debe procurar que al registrar elementos en el arreglo, los elementos mayores se encuentren a la izquierda -de modo que el mayor elemento insertado tenga índice 0 en el arreglo- mientras que los menores sean almacenados a la derecha, lo que implica que el menor elemento insertado se encuentre en la posición nItems -1 del arreglo. En la siguiente imagen:

La flecha Rear apunta hacia el elemento de mayor valor, que tiene el índice 0 en el arreglo; mientras que la flecha Front apunta hacia el elemento de menor valor con índice nItems -1 en el arreglo de PriorityQ. Al ingresar un elemento mediante el método insert, debemos procurar que este criterio se mantenga; por lo que realizamos lo siguiente:

• En caso el arreglo no tenga elementos, el nuevo elemento ingresado ocupará la posición 0 del arreglo. Al realizar un registro, siempre se incrementa el valor de  nItems de modo que este atributo siempre contenga el número de elementos de la Cola.
• En caso el arreglo no esté vacío, compararemos el elemento a ingresar con cada uno de los elementos del arreglo empezando por el menor-el de índice  (nItems  -1 )- desplazando los elementos existentes hacia la derecha hasta encontrar el lugar apropiado para el nuevo elemento de modo que el arreglo se mantenga ordenado.

Con esa lógica de inserción aseguramos que al invocar a remove siempre obtendremos el menor elemento de la lista, que es el primero de la Cola. Dado que realizamos comparaciones a lo largo del arreglo al momento de insertar, el tiempo de inserción es directamente proporcional al número de elementos de la Cola; sin embargo, el método remove tiene un tiempo de ejecución constante y no depende del número de elementos de la cola.

Para finalizar, las colas de prioridades se aplican -por ejemplo- en los sistemas operativos multi-tarea. Los procesos se colocan en una Cola de Prioridades y es un función a la prioridad/importancia relativa que les da el sistema operativo que pueden acceder a recursos como el CPU.

Código fuente e imágenes tomadas de Data Structures and Algorithms in Java.