Cola de prioridad en Java

De vez en cuando, necesitamos procesar elementos de una cola en un orden específico. La cola de prioridad es una estructura de datos que realiza esta tarea. La cola de prioridad en Java es diferente de una cola “normal”. En lugar de seguir el principio de “el primero en entrar, el primero en salir”, recupera los elementos según su prioridad.

Cola de Prioridad en Java

La clase java.util.PriorityQueue nos proporciona una implementación de este tipo de dato, utilizando internamente una implementación de montículo de prioridad. La PriorityQueue en Java es una cola sin límites. Se introdujo en Java 1.5 y se mejoró en la versión Java SE 8. Internamente, PriorityQueue se implementa siguiendo la estructura de datos “Montículo de Prioridad”. Aquí tienes la jerarquía de clases de la PriorityQueue: Diagrama de Clase de la PriorityQueue:

Constructores de PriorityQueue en Java

1. PriorityQueue() – Crea una PriorityQueue con la capacidad inicial predeterminada, es decir, 11
2. PriorityQueue(Collection c) – Crea una PriorityQueue con los elementos en la colección especificada
3. PriorityQueue(int initialCapacity) – Crea una PriorityQueue con la capacidad inicial especificada
4. PriorityQueue(int initialCapacity, Comparator comparator) – Crea una PriorityQueue con la capacidad inicial proporcionada y el orden de sus elementos según el comparador especificado
5. PriorityQueue(PriorityQueue c) – Crea una PriorityQueue que contiene los elementos en la cola de prioridad especificada
6. PriorityQueue(SortedSet c) – Crea una PriorityQueue que contiene los elementos en el conjunto ordenado especificado

Los elementos de la cola de prioridad están ordenados por su orden natural a menos que proporcionemos un Comparator al crearlo. Los elementos se ordenan de forma ascendente por defecto, por lo tanto, la cabeza de la cola es el elemento cuya prioridad es la más baja. Si hay dos elementos que son elegibles para convertirse en la cabeza al mismo tiempo, este tipo de empates se rompen arbitrariamente.

Ejemplo de Java PriorityQueue

Creemos una PriorityQueue, que contenga varias tareas:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

Esto crea una PriorityQueue de tareas, que se ordenarán por el orden natural de String. Creemos otra PriorityQueue que ordene las tareas en orden inverso al orden natural. Por lo tanto, necesitamos pasar un Comparator:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Métodos de PriorityQueue de Java

Ahora, echemos un vistazo a todos los métodos disponibles para PriorityQueue y úsalos:

1. Boolean add(E e) – Este método inserta el elemento especificado en la cola. Ya hemos agregado 5 tareas en nuestra cola usando este método.

2. Comparator comparator() – Este método devuelve el comparador utilizado para ordenar los elementos en esta cola. Devuelve null si no se especificó ningún comparador y la cola se ordena según el orden natural de sus elementos. Entonces, si hacemos:

   System.out.println(tasks.comparator());
   System.out.println(reverseTasks.comparator());
   

   La salida será:

   null
   java.util.Collections$ReverseComparator@15db9742
   

3. boolean contains(Object o) – Devuelve true si la cola contiene el elemento especificado. Veamos si “tarea3” pertenece a la cola de prioridad de tareas:

   System.out.println(tareas.contains("tarea3"));
   

   Esto imprime:

   true
   

4. boolean offer(E e) – Al igual que el método add(), este método también agrega un elemento a la cola. Los métodos offer() y add() son un poco diferentes para colas con capacidad limitada, pero en el caso de PriorityQueue, ambos son iguales. A diferencia de add(), offer() no arroja una excepción incluso si no puede agregar el elemento en la cola.

5. E peek() – Recupera la cabeza de esta cola, o devuelve null si esta cola está vacía. En otras palabras, devuelve el elemento con mayor prioridad. Entonces, el siguiente código:

   System.out.println(tareas.peek());
   System.out.println(tareasInversa.peek());
   

   Nos da:

   tarea1
   tarea5
   

6. E poll() – Este método también recupera la cabeza de la cola (el elemento con mayor prioridad) o devuelve nulo si la cola está vacía. Pero a diferencia de peek(), también elimina el elemento. Entonces, si llamamos a poll():

   System.out.println(“Poll en tareas: ”+tasks.poll());
   System.out.println(“Poll en reverseTasks: ”+reverseTasks.poll());
   

   Y luego peek:

   System.out.println(“Peek en tareas: ”+tasks.peek());
   System.out.println(“Peek en reverseTasks: ”+reverseTasks.peek());
   

   Tendremos la siguiente salida:

   Poll en tareas: tarea1
   Poll en reverseTasks: tarea5
   Peek en tareas: tarea2
   Peek en reverseTasks: tarea4
   

7. int size() – Devuelve el número de elementos en la cola.

8. boolean remove(Object o) – Elimina el elemento especificado de la cola, si está presente. Si hay dos elementos iguales, solo elimina uno de ellos.

9. Object[] toArray() – Devuelve un array que contiene todos los elementos en la cola.

10. T[] toArray(T[] a) – Devuelve un arreglo que contiene todos los elementos en la cola, y el tipo del arreglo devuelto es el especificado.

11. Iterator iterator() – Devuelve un iterador para la cola.

12. void clear() – Elimina todos los elementos de la cola.

Además de estos, la PriorityQueue también hereda los métodos de las clases Collection y Object.

Complejidad Temporal de la Cola de Prioridad en Java

1. Para los métodos de inserción y eliminación, la complejidad temporal es O(log(n)).
2. Para los métodos remove(Object) y contains(Object), la complejidad temporal es lineal.
3. Para los métodos de recuperación, tiene una complejidad temporal constante.

Esta implementación de la cola de prioridad no es segura para hilos. Por lo tanto, si necesitamos acceso sincronizado, necesitamos usar PriorityBlockingQueue. Referencia: Documentación de la API