Artigo original: https://www.freecodecamp.org/news/priority-queue-implementation-in-java/

Filas de prioridades geralmente são usadas em aplicações da vida real. Neste artigo, aprenderemos o que são essas filas e como podemos usá-las em Java.

Antes de discutirmos o que é uma fila de prioridades, vejamos o que é uma fila regular.

Uma fila (ou, em inglês, queue) regular segue a estrutura em que o primeiro a entrar é o primeiro a sair (em inglês, first in first out, também conhecida pela abreviação FIFO). Isso significa que, se 3 mensagens – m1, m2 e m3 – entrarem na fila nessa ordem, elas sairão da fila exatamente na mesma ordem.

Por que precisamos de filas?

Vamos supor que tenhamos produtores de dados (por exemplo, quando um usuário clica em uma página da web) que são extremamente rápidos. Queremos, no entanto, consumir esses dados em um ritmo mais lento posteriormente.

Nesse caso, o produtor dos dados enviaria todas as mensagens para a fila e o consumidor as receberia mais tarde, vindas da fila, em um ritmo mais lento.

O que é uma fila de prioridades?

Como mencionamos anteriormente, uma fila regular segue a estrutura em que o primeiro a entrar é o primeiro a sair. Em alguns cenários, contudo, queremos processar as mensagens de uma fila com base em sua prioridade, não na ordem em que entraram na fila.

As filas de prioridades ajudam a consumir as mensagens de prioridade mais alta primeiro, seguidas daquelas com prioridade mais baixa.

Filas de prioridades em Java

Vamos agora ver um código real em Java que nos mostrará como usar filas de prioridades.

Filas de prioridades com ordenamento natural

Aqui vemos um código mostrando como criar uma fila de prioridades simples para strings

private static void testStringsNaturalOrdering() {
        Queue<String> testStringsPQ = new PriorityQueue<>();
        testStringsPQ.add("abcd");
        testStringsPQ.add("1234");
        testStringsPQ.add("23bc");
        testStringsPQ.add("zzxx");
        testStringsPQ.add("abxy");

        System.out.println("Strings armazenadas por ordenamento natural em uma fila de prioridades\n");
        while (!testStringsPQ.isEmpty()) {
            System.out.println(testStringsPQ.poll());
        }
    }

A primeira linha nos informa que estamos criando uma fila de prioridades:

Queue<String> testStringsPQ = new PriorityQueue<>();

PriorityQueue está disponível no pacote java.util.

Em seguida, adicionamos 5 strings em ordem aleatória na fila de prioridades. Para isso, usamos a função add(), como vemos abaixo:

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

Para obter o item mais recente da fila, usamos a função poll(), deste modo:

testStringsPQ.poll()

poll() nos dará o item mais recente e o removerá da fila. Se quisermos obter o item mais recente da fila sem removê-lo, podemos usar a função peek():

testStringsPQ.peek()

Por fim, imprimimos todos os elementos da fila usando a função poll(), assim:

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

Aqui vemos o resultado do programa acima:

1234
23bc
abcd
abxy
zzxx

Como não demos à fila de prioridades uma maneira de priorizar seu conteúdo, foi usado o ordenamento natural padrão. Nesse caso, recebemos os dados na ordem ascendente das strings. Essa não é a mesma ordem na qual os itens foram adicionados à fila.

Como conseguir um ordenamento personalizado?

Isso também é possível. Conseguimos fazer isso com a ajuda de um comparador (em inglês, comparator).

Vamos criar agora uma fila de prioridades de números inteiros. Desta vez, no entanto, vamos obter o resultado em ordem descendente de valores.

Para conseguir isso, primeiro precisamos criar um comparator de número inteiros:

 static class CustomIntegerComparator implements Comparator<Integer> {

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

Para criar um comparator, implementamos a interface comparator e sobrescreveremos o método compare.

Usando o1 < o2 ? 1 : -1, obteremos o resultado em ordem descendente. Se tivéssemos usado o1 > o2 ? 1 : -1, obteríamos o resultado em ordem ascendente.

Agora que já temos o comparator, precisamos adicioná-lo à fila de prioridades. Podemos fazer isso da seguinte maneira:

Queue<Integer> testIntegersPQ = new PriorityQueue<>(new CustomIntegerComparator());

Aqui vemos o resto do código que adicionará elementos à fila de prioridades e os mostrará na tela:

   testIntegersPQ.add(11);
        testIntegersPQ.add(5);
        testIntegersPQ.add(-1);
        testIntegersPQ.add(12);
        testIntegersPQ.add(6);

        System.out.println("Números inteiros armazenados em ordem inversa na fila de prioridades\n");
        while (!testIntegersPQ.isEmpty()) {
            System.out.println(testIntegersPQ.poll());
        }

O resultado do programa acima é este:

12
11
6
5
-1

Podemos ver que o comparator fez bem o seu trabalho. Agora, a fila de prioridades nos dá os números inteiros em ordem descendente.

Fila de prioridades com objetos do Java

Até este ponto, vimos como podemos usar strings e números inteiros com as filas de prioridades.

Na vida real, as aplicações geralmente usariam filas de prioridades com objetos personalizados do Java.

Para começar, vamos criar uma classe chamada CustomerOrder (em português, pedido do cliente), que será usada para armazenar os detalhes dos pedidos dos clientes:

public class CustomerOrder implements Comparable<CustomerOrder> {
    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;
    }
}

Esse é um caso simples de classes em Java para armazenar pedidos de clientes. Essa classe implementa a interface Comparable, de modo que possamos decidir como esse objeto precisa ser ordenado na fila de prioridades.

O ordenamento é decidido pela função compareTo no código acima. A linha o.orderId > this.orderId ? 1 : -1 orienta a fila a ordenar em ordem descendente com base no campo orderId.

Abaixo vemos o código que cria uma fila de prioridades para o 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<CustomerOrder> customerOrders = new PriorityQueue<>();
customerOrders.add(c1);
customerOrders.add(c2);
customerOrders.add(c3);
while (!customerOrders.isEmpty()) {
	System.out.println(customerOrders.poll());
}

No código acima, três pedidos de clientes foram criados e adicionados à fila de prioridades.

Ao executarmos o código, teremos o seguinte resultado:

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

Como esperávamos, o resultado vem em ordem descendente com base no campo orderId.

Como faríamos para priorizar com base no campo orderAmount?

Mais uma vez, temos um cenário da vida real. Digamos que, por padrão, o objeto CustomerOrder é priorizado pelo campo orderId. No entanto, precisamos de um modo de priorizá-lo com base no campo orderAmount (em português, valor do pedido).

Você pode pensar de imediato que deveremos modificar a função compareTo na classe CustomerOrder para ordenar com base no campo orderAmount.

A classe CustomerOrder, no entanto, pode ser usada em diversos lugares da aplicação. Modificar a função compareTo diretamente interferiria com o resto da aplicação, portanto.

A solução para isso é bastante simples: podemos criar um comparator personalizado para a classe CustomerOrder e usá-lo em conjunto com a fila de prioridades.

Abaixo, vemos o código para o comparator personalizado:

 static class CustomerOrderComparator implements Comparator<CustomerOrder> {

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

Ele é bastante semelhante ao comparator personalizado de números inteiros que vimos anteriormente.

A linha o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; indica que precisamos priorizar com base na ordem descendente de orderAmount.

Aqui vemos o código que cria a fila de prioridades:

  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<CustomerOrder> customerOrders = new PriorityQueue<>(new CustomerOrderComparator());
        customerOrders.add(c1);
        customerOrders.add(c2);
        customerOrders.add(c3);
        while (!customerOrders.isEmpty()) {
            System.out.println(customerOrders.poll());
        }

No código acima, passamos o comparator para a fila de prioridades na linha de código que diz:

Queue<CustomerOrder> customerOrders = new PriorityQueue<>(new CustomerOrderComparator());

Abaixo, vemos o resultado ao executar esse código:

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

Podemos ver que os dados vêm em ordem descendente com base no campo orderAmount.

Código

Todo o código que discutimos neste artigo pode ser encontrado neste repositório do GitHub.

Parabéns!

Você, agora, sabe como usar filas de prioridades em Java.

Sobre o autor

O autor é um apaixonado por tecnologia e segue os avanços no campo. Ele também gosta de auxiliar as outras pessoas com seu conhecimento em tecnologia.

Você pode entrar em contato com ele por sua conta no LinkedIn.

Você também pode seguir o autor no Twitter.

Por fim, você pode ler mais artigos escritos por ele (em inglês) no blog do autor.