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 realiza essa tarefa. A fila de prioridade em Java difere da fila “normal”. Em vez de seguir o princípio “Primeiro a Entrar, Primeiro a Sair” (FIFO), ela recupera os itens de acordo com a prioridade deles.

Fila de Prioridade em Java

A classe java.util.PriorityQueue nos fornece uma implementação desse tipo de dado, utilizando internamente uma implementação de heap de prioridade. A PriorityQueue em Java é uma fila ilimitada, introduzida no Java 1.5 e aprimorada na versão Java SE 8. Ela é implementada internamente seguindo a estrutura de dados “Heap de Prioridade”. Aqui está a hierarquia de classes da PriorityQueue: Diagrama de Classes da 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. PriorityQueue(int initialCapacity) – Cria uma PriorityQueue com a capacidade inicial especificada
  4. PriorityQueue(int initialCapacity, Comparator comparator) – Cria uma PriorityQueue com a capacidade inicial fornecida e a ordenação de seus elementos é de acordo com o comparador especificado
  5. PriorityQueue(PriorityQueue c) – Cria uma PriorityQueue contendo os elementos na fila de prioridade especificada
  6. PriorityQueue(SortedSet c) – Cria uma PriorityQueue contendo os elementos no conjunto ordenado especificado

Os elementos da fila de prioridade são ordenados pela sua ordenação natural, a menos que forneçamos um Comparator ao criá-lo. Os elementos são ordenados em ordem ascendente por padrão, portanto, a cabeça da fila é o elemento cuja prioridade é mais baixa. Se houver dois elementos que são elegíveis para se tornarem a cabeça ao mesmo tempo, esse tipo de empate é quebrado arbitrariamente.

Exemplo de PriorityQueue em Java

Vamos criar uma PriorityQueue, 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 PriorityQueue de tarefas, que serão ordenadas pela ordenação natural de String. Vamos criar outra PriorityQueue que ordena as tarefas na ordem inversa da ordenação 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 do Java

Agora, vamos dar uma olhada em todos os métodos disponíveis para PriorityQueue e usá-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 ordem natural de seus elementos. Portanto, se fizermos:

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

    A saída será:

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – Retorna true se a fila contiver o elemento especificado. Vamos verificar se “task3” pertence à fila de prioridade tasks:

    System.out.println(tasks.contains("task3"));

    Isto imprime:

    true

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

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

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

    Nos dá:

    task1
task5

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

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

    E então peek:

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

    Teremos a seguinte saída:

    Poll em tarefas: tarefa1
Poll em reverseTasks: tarefa5
Peek em tarefas: tarefa2
Peek em reverseTasks: tarefa4

  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, 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, o PriorityQueue também herda os métodos das classes Collection e Object.

Complexidade de Tempo da PriorityQueue em Java

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

Esta implementação de fila de prioridade não é à prova de threads. Portanto, se precisarmos de acesso sincronizado, precisamos usar PriorityBlockingQueue. Referência: Documentação da API

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