Colas de prioridad en Java explicadas con ejemplos

Las colas de prioridad se utilizan con mucha frecuencia en aplicaciones de la vida real. En este artículo aprenderemos qué son las colas de prioridad y cómo podemos usarlas en Java.

Antes de discutir qué es una cola de prioridad, veamos qué es una cola normal.

Una cola normal sigue una estructura de primero en entrar, primero en salir (FIFO). Esto significa que si 3 mensajes (m1, m2 y m3) entran en la cola en ese orden, entonces salen de la cola exactamente en el mismo orden.

¿Por qué necesitamos colas?

Digamos que tenemos productores de datos (por ejemplo, cuando un usuario hace clic en una página web) que son extremadamente rápidos. Pero luego queremos consumir estos datos a un ritmo más lento más adelante.

En este caso, el productor enviaría todos los mensajes a la cola y un consumidor consumiría estos mensajes más tarde de la cola a un ritmo más lento.

¿Qué es una cola de prioridad?

Como se mencionó anteriormente, una cola normal tiene una estructura de primero en entrar, primero en salir. Pero en algunos escenarios queremos procesar mensajes en una cola según su prioridad y no según el momento en que el mensaje entró en la cola.

Las colas de prioridad ayudan a los consumidores a consumir primero los mensajes de mayor prioridad y luego los de menor prioridad.

Colas de prioridad en Java

Ahora veamos algo de código Java real que nos mostrará cómo usar las colas de prioridad.

Colas prioritarias con ordenamiento natural

Aquí hay un código que muestra cómo crear una cola de prioridad simple para cadenas

private static void testStringsNaturalOrdering() { Queue testStringsPQ = new PriorityQueue(); testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy"); System.out.println("Strings Stored in Natural Ordering in a Priority Queue\n"); while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); } }

La primera línea nos dice que estamos creando una cola de prioridad:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue está disponible en el paquete java.util.

A continuación, agregamos 5 cadenas en orden aleatorio en la cola de prioridad. Para esto usamos la función add () como se muestra a continuación:

testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy");

Para obtener el último elemento de la cola, usamos la función poll () como se muestra a continuación:

testStringsPQ.poll()

poll () nos dará el último elemento y también lo eliminará de la cola. Si queremos obtener el último elemento de la cola sin eliminarlo, podemos usar la función peek () :

testStringsPQ.peek()

Finalmente, imprimimos todos los elementos de la cola usando la función poll () como se muestra a continuación:

while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); }

Aquí está el resultado del programa anterior:

1234 23bc abcd abxy zzxx

Como no le dijimos a la cola de prioridad cómo priorizar su contenido, usó un orden natural predeterminado. En este caso, nos devolvió los datos en el orden ascendente de las cadenas. Este no es el mismo orden en el que se agregaron los elementos a la cola.

¿Qué hay de tener un pedido personalizado?

Esto también es posible y podemos hacerlo con la ayuda de un comparador.

Creemos ahora una cola de prioridad entera. Pero esta vez obtengamos el resultado en orden descendente de valor.

Para lograr esto, primero necesitamos crear un comparador de enteros:

 static class CustomIntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 < o2 ? 1 : -1; } }

Para crear un comparador, implementamos la interfaz del comparador y anulamos el método de comparación .

Utilizando o1 <o2? 1: -1 obtendremos el resultado en orden descendente. Si hubiéramos usado o1> o2? 1: -1, entonces habríamos obtenido el resultado en orden ascendente

Ahora que tenemos el comparador, debemos agregar este comparador a la cola de prioridad. Podemos hacer esto así:

Queue testIntegersPQ = new PriorityQueue(new CustomIntegerComparator());

Aquí está el resto del código que agrega elementos a la cola de prioridad y los imprime:

 testIntegersPQ.add(11); testIntegersPQ.add(5); testIntegersPQ.add(-1); testIntegersPQ.add(12); testIntegersPQ.add(6); System.out.println("Integers stored in reverse order of priority in a Priority Queue\n"); while (!testIntegersPQ.isEmpty()) { System.out.println(testIntegersPQ.poll()); }

El resultado del programa anterior se da a continuación:

12 11 6 5 -1

Podemos ver que el comparador ha hecho bien su trabajo. Ahora la cola de prioridad nos da los números enteros en orden descendente.

Cola de prioridad con objetos Java

Hasta este punto, hemos visto cómo podemos usar cadenas y enteros con colas de prioridad.

En aplicaciones de la vida real, generalmente estaríamos usando colas de prioridad con objetos Java personalizados.

Primero creemos una clase llamada CustomerOrder que se usa para almacenar los detalles del pedido del cliente:

public class CustomerOrder implements Comparable { private int orderId; private double orderAmount; private String customerName; public CustomerOrder(int orderId, double orderAmount, String customerName) { this.orderId = orderId; this.orderAmount = orderAmount; this.customerName = customerName; } @Override public int compareTo(CustomerOrder o) { return o.orderId > this.orderId ? 1 : -1; } @Override public String toString() { return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName; } public double getOrderAmount() { return orderAmount; } }

Esta es una clase Java simple para almacenar pedidos de clientes. Esta clase implementa una interfaz comparable, de modo que podemos decidir sobre qué base se debe ordenar este objeto en la cola de prioridad.

El orden se decide mediante la función compareTo en el código anterior. La línea o.orderId> this.orderId? 1: -1 indica que los pedidos deben ordenarse según el orden descendente del campo orderId

A continuación se muestra el código que crea una cola de prioridad para el objeto CustomerOrder:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

En el código anterior, se han creado tres pedidos de clientes y se han agregado a la cola de prioridad.

Cuando ejecutamos este código obtenemos el siguiente resultado:

orderId:3, orderAmount:50.0, customerName:customer3 orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1

Como se esperaba, el resultado viene en orden descendente del orderId .

¿Qué pasa si queremos priorizar en función de orderAmount?

Este es nuevamente un escenario de la vida real. Digamos que, de forma predeterminada, el objeto CustomerOrder tiene la prioridad del orderId. Pero luego necesitamos una forma en la que podamos priorizar en función de orderAmount.

Puede pensar inmediatamente que podemos modificar la función compareTo en el c lass CustomerOrder para ordenar según orderAmount.

Pero la class CustomerOrder se puede usar en varios lugares de la aplicación, e interferiría con el resto de la aplicación si modificamos la función compareTo directamente.

La solución a esto es bastante simple: podemos crear un nuevo comparador personalizado para la clase CustomerOrder y usarlo junto con la cola de prioridad

A continuación se muestra el código del comparador personalizado:

 static class CustomerOrderComparator implements Comparator { @Override public int compare(CustomerOrder o1, CustomerOrder o2) { return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; } }

Esto es muy similar al comparador de enteros personalizado que vimos anteriormente.

La línea o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1;indica que debemos priorizar en función del orden descendente de orderAmount .

A continuación se muestra el código que crea la cola de prioridad:

 CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(new CustomerOrderComparator()); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code we are passing the comparator to the priority queue in the following line of code:

Queue customerOrders = new PriorityQueue(new CustomerOrderComparator());

Below is the result when we run this code:

orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1 orderId:3, orderAmount:50.0, customerName:customer3

We can see that the data comes in descending order of the orderAmount.

Code

All the code discussed in this article can be found in this GitHub repo.

Congrats ?

You now know how to use priority queues in Java.

About the author

I love technology and follow the advancements in the field. I also like helping others with my technology knowledge.

Feel free to connect with me on my LinkedIn account //www.linkedin.com/in/aditya1811/

You can also follow me on twitter //twitter.com/adityasridhar18

Feel free to read more of my articles on my blog at adityasridhar.com.