Fila de Prioridade em Java

Tutoriais
Java

De vez em quando, precisamos processar itens de uma fila em uma ordem específica. A fila de prioridade é uma estrutura de dados que faz esse trabalho. A fila de prioridade em Java é diferente da “fila” normal. Em vez de “Primeiro a entrar, primeiro a sair”, ela recupera os itens de acordo com sua prioridade.

Fila de Prioridade em Java

A classe java.util.PriorityQueue nos fornece uma implementação desse tipo de dado, usando uma implementação interna de heap de prioridade. A PriorityQueue em Java é uma fila não limitada. Ela foi introduzida no Java 1.5 e aprimorada no lançamento do Java SE 8. A PriorityQueue é implementada internamente seguindo a estrutura de dados “Heap de Prioridade”. Aqui está a hierarquia de classes da PriorityQueue: Diagrama de Classe PriorityQueue:

Construtores da PriorityQueue em Java

  1. PriorityQueue() – Cria uma PriorityQueue com a capacidade inicial padrão, ou seja, 11
  2. PriorityQueue(Collection c) – Cria uma PriorityQueue com os elementos na coleção especificada
  3. FilaDePrioridade(int capacidadeInicial) – Cria uma Fila de Prioridade com a capacidade inicial especificada
  4. FilaDePrioridade(int capacidadeInicial, Comparador comparador) – Cria uma Fila de Prioridade com a capacidade inicial fornecida e a ordem de seus elementos é de acordo com o comparador especificado
  5. FilaDePrioridade(FilaDePrioridade c) – Cria uma Fila de Prioridade contendo os elementos na fila de prioridade especificada
  6. FilaDePrioridade(ConjuntoOrdenado c) – Cria uma Fila de Prioridade contendo os elementos no conjunto ordenado especificado

Os elementos da Fila de Prioridade são ordenados pelo seu ordenamento natural, a menos que forneçamos um Comparador ao criá-lo. Os elementos são ordenados em ordem ascendente por padrão, portanto, o início da fila é o elemento com a prioridade mais baixa. Se houver dois elementos elegíveis para se tornarem o início ao mesmo tempo, essas amarras são quebradas arbitrariamente.

Exemplo de Fila de Prioridade em Java

Vamos criar uma FilaDePrioridade, contendo várias tarefas:

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

Isso cria uma Fila de Prioridade de tarefas, que será ordenada pelo ordenamento natural de String. Vamos criar outra Fila de Prioridade que ordena as tarefas em ordem reversa do ordenamento natural. Portanto, precisamos passar um Comparador:

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

Métodos da PriorityQueue em Java

Agora, vamos dar uma olhada em todos os métodos disponíveis para PriorityQueue e utilizá-los:

  1. Boolean add(E e) – Este método insere o elemento especificado na fila. Já adicionamos 5 tarefas em nossa fila usando este método.

  2. Comparator comparator() – Este método retorna o Comparator usado para ordenar os elementos nesta fila. Ele retorna null se nenhum comparador foi especificado e a fila é ordenada de acordo com a ordenação natural de seus elementos. Portanto, se fizermos:

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

    O resultado será:

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contém(Object o) – Retorna verdadeiro se a fila contiver o elemento especificado. Vamos verificar se “tarefa3” pertence à fila de prioridade de tarefas:

    System.out.println(tarefas.contém("tarefa3"));

    Isto imprime:

    verdadeiro

  4. boolean oferecer(E e) – Assim como o método add(), este método também adiciona um elemento à fila. Os métodos oferecer() e add() são um pouco diferentes para filas com capacidade restrita, mas no caso de PriorityQueue, ambos são iguais. Diferente do add(), o oferecer() não lança uma exceção mesmo se falhar ao adicionar o elemento na fila.

  5. E espiar() – Recupera o cabeçalho desta fila, ou retorna nulo se esta fila estiver vazia. Em outras palavras, ele retorna o elemento com a maior prioridade. Então o seguinte código:

    System.out.println(tarefas.espiar());
System.out.println(tarefasInvertidas.espiar());

    Nos dá:

    tarefa1
tarefa5

  6. E poll() – Este método também recupera o cabeçalho da fila (elemento com a maior prioridade) ou retorna nulo se a fila estiver vazia. Mas, ao contrário do peek(), ele também remove o elemento. Então, se chamarmos poll():

    System.out.println("Poll em tasks: "+tasks.poll());
System.out.println("Poll em reverseTasks: "+reverseTasks.poll());

    E então peek:

    System.out.println("Peek em tasks: "+tasks.peek());
System.out.println("Peek em reverseTasks: "+reverseTasks.peek());

    Teremos a seguinte saída:

    Poll em tasks: task1
Poll em reverseTasks: task5
Peek em tasks: task2
Peek em reverseTasks: task4

  7. int size() – Retorna o número de elementos na fila.

  8. boolean remove(Object o) – Remove o elemento especificado da fila, se estiver presente. Se dois elementos iguais estiverem presentes, ele remove apenas um deles.

  9. Object[] toArray() – Retorna um array contendo todos os elementos na fila.

  10. T[] toArray(T[] a) – Retorna um array contendo todos os elementos na fila, e o tipo do array retornado é o mesmo do array especificado.

  11. Iterator iterator() – Retorna um iterador para a fila.

  12. void clear() – Remove todos os elementos da fila.

Além desses, a PriorityQueue também herda os métodos das classes Collection e Object.

Complexidade Temporal da PriorityQueue em Java

  1. Para os métodos de inserção e remoção, a complexidade temporal é O(log(n))
  2. Para os métodos remove(Object) e contains(Object), a complexidade temporal é linear
  3. Para os métodos de recuperação, a complexidade temporal é constante

Esta implementação de fila de prioridade não é segura para threads. Portanto, se precisarmos de acesso sincronizado, precisamos usar PriorityBlockingQueue. Referência: API Doc

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java