Java Priority Queue: não é uma fila clássica

Neste artigo, aprendemos uma fila de prioridade, classe Java, que implementa a interface Queue. O que um programador sabe sobre interface de fila regular? Em primeiro lugar, esta interface é baseada no princípio FIFO ou “first in first out”. Isso lembra uma fila regular em seu significado comum. Você quer tomar um café no McDrive? Se o seu carro for o primeiro próximo à janela, você tomará seu café antes do próximo motorista.

Declaração de interface de fila

public interface Queue<E> extends Collection<E>

O que é uma fila prioritária

O que é uma fila prioritária? Em primeiro lugar, é uma classe que implementa a interface Queue no caso de inserir um elemento por trás e remover um elemento pela cabeça. No entanto, não é uma fila normal lá dentro. A ordem dos elementos da fila de prioridade Java depende da prioridade dos elementos. O elemento com maior prioridade será movido para o início da fila. Se você deletar (servir) o elemento com classificação mais alta, o segundo vai para a cabeça pegar seu café. Como é determinada a prioridade? Segundo a documentação, os elementos da fila de prioridade são ordenados de acordo com sua ordem natural, ou por um Comparator fornecido no momento da construção da fila, dependendo de qual construtor for utilizado. Uma fila de prioridade baseada em um heap mínimo de prioridade. Isso significa que, no caso de elementos de fila de números, o primeiro elemento da fila será o mínimo desses números. Muitas vezes, depois de ler esta definição, os alunos novatos começam a pensar que a fila de prioridade é classificada de forma linear. Ou seja, se, digamos, usarmos uma fila cujos elementos são números naturais, o primeiro elemento será o menor e o último - o maior. Isso não é inteiramente verdade. Para entender como a fila de prioridade realmente funciona e o que ela oferece, você precisa descobrir como funciona o heap. Consideramos a estrutura interna da fila de prioridade usando um exemplo um pouco mais tarde. Agora vamos nos debruçar sobre seus atributos externos. então o primeiro elemento será o menor e o último - o maior. Isso não é inteiramente verdade. Para entender como a fila de prioridade realmente funciona e o que ela oferece, você precisa descobrir como funciona o heap. Consideramos a estrutura interna da fila de prioridade usando um exemplo um pouco mais tarde. Agora vamos nos debruçar sobre seus atributos externos. então o primeiro elemento será o menor e o último - o maior. Isso não é inteiramente verdade. Para entender como a fila de prioridade realmente funciona e o que ela oferece, você precisa descobrir como funciona o heap. Consideramos a estrutura interna da fila de prioridade usando um exemplo um pouco mais tarde. Agora vamos nos debruçar sobre seus atributos externos.

Construtores e declaração da classe PriorityQueue

A classe PriorityQueue fornece 6 maneiras diferentes de construir uma fila de prioridade em Java.

• PriorityQueue() - fila vazia com capacidade inicial padrão (11) que ordena seus elementos de acordo com sua ordem natural.
• PriorityQueue(Collection c) - fila vazia contendo os elementos na coleção especificada.
• PriorityQueue(int initialCapacity) - fila vazia com a capacidade inicial especificada que ordena seus elementos de acordo com sua ordem natural.
• PriorityQueue(int initialCapacity, Comparator comparator) - fila vazia com a capacidade inicial especificada que ordena seus elementos de acordo com o comparador especificado.
• PriorityQueue(PriorityQueue c) - fila vazia contendo os elementos na fila de prioridade especificada.
• PriorityQueue(SortedSet c) - fila vazia contendo os elementos no conjunto classificado especificado.

A fila de prioridade em Java é declarada da seguinte maneira:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Criando fila prioritária

Vamos criar uma fila prioritária de números inteiros. Implementação da fila prioritária, código Java:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Criamos uma fila de prioridade sem argumentos. Nesse caso, o início da fila de prioridade é o número mínimo da fila. Se você remover a cabeça, o próximo menor elemento ocupará este lugar. Assim, você pode remover elementos da fila em ordem crescente. Se necessário, você pode alterar o princípio de ordenação usando a interface Comparator.

Métodos Java PriorityQueue

A classe Java PriorityQueue possui métodos importantes para adicionar, remover e verificar elementos.

Inserir elementos na fila de prioridade

• boolean add(object) insere o elemento especificado na fila de prioridade. Retorna verdadeiro em caso de sucesso. Se a fila estiver cheia, o método lançará uma exceção.
• boolean offer(object) insere o elemento especificado nesta fila de prioridade. Se a fila estiver cheia, o método retorna false.

Você pode usar ambas as operações de adição, não há diferenças para a maioria dos casos. Aqui está um pequeno exemplo de inicialização e adição de elementos na fila de prioridade.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

A saída é:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

A ordem dos elementos parece estranha, explicaremos mais adiante.

Recuperando e removendo elementos da fila de prioridade

• boolean remove(object) remove uma única instância do elemento especificado desta fila, se estiver presente.
• Object poll() recupera e remove o início desta fila. Retorna nulo se a fila estiver vazia.
• void clear() remove todos os elementos da fila de prioridade.
• Object element() recupera o início desta fila sem removê-lo. Lança NoSuchElementException se a fila estiver vazia.
• Object peek() recupera o início da fila sem removê-lo. Retorna nulo se a fila estiver vazia.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

A saída:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Como você pode ver, tentar imprimir o cabeçalho da Fila vazia usando o método element() leva a NoSuchElementeException .

Comparador de filas prioritárias

• Comparator comparator() retorna o comparador usado para ordenar os elementos na fila. Retorna nulo se a fila for classificada de acordo com a ordem natural de seus elementos.

Fila de prioridade Java, exemplo com comparador

Usamos ordem natural (ascendente) nos exemplos de código acima, mas às vezes devemos alterá-la. Aqui está um exemplo de fila de prioridade Java, onde criamos nossa própria classe de comparação interna que implementa a interface Comparator. Nosso comparador classificará os elementos do maior para o menor.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

A saída:

the head of Queue = 5
5
4
3
2
1

A cabeça da fila agora não é o elemento mínimo, mas máximo, e a ordem foi alterada para inversa.

Iterando sobre PriorityQueue usando o iterador

ProrityQueue faz parte da estrutura Collection e implementa a interface Iterable<> . Para iterar sobre os elementos de uma fila de prioridade, você pode usar o método iterator() . Aqui está um exemplo:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

A saída:

1 2 4 5 3 

Mais métodos PriorityQueue

• boolean contains(Object o) retorna true se a fila contiver o elemento o.
• int size() retorna o número de elementos nesta fila.
• Object[] toArray() retorna um array contendo todos os elementos nesta fila.

Aqui está um exemplo:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

A saída:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Definição de PriorityQueue Java 8

Se você abrir a documentação do java 8 priorityqueue, encontrará a próxima definição: Uma fila de prioridade ilimitada baseada em um heap de prioridade. Os elementos da fila de prioridade são ordenados de acordo com sua ordem natural, ou por um Comparator fornecido no momento da construção da fila, dependendo de qual construtor é utilizado. Uma fila de prioridade não permite elementos nulos. Uma fila de prioridade baseada na ordem natural também não permite a inserção de objetos não comparáveis ​​(isso pode resultar em ClassCastException). Heap é uma palavra muito importante aqui. Ele explica as propriedades de ordenação dos elementos da Fila de Prioridade.

O princípio do trabalho de PriorityQueue: pilha binária

Vamos começar com um exemplo. Vamos criar dois objetos implementando a interface Queue. Um deles LinkedList, o segundo — PriorityQueue. Ambos têm 5 elementos inteiros (1,2,3,4 e 5) e começamos a colocar os elementos em nossas filas do maior para o menor. Assim, o primeiro vem 5, depois 4, 3, 2 e o último será 1. Em seguida, imprima as duas listas para verificar a ordem.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

O resultado desses códigos funcionando é o seguinte:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Bem, a ordem da lista vinculada é previsível e compreensível. É ordenado de acordo com o princípio FIFO. Começamos com 5, então esse elemento é o primeiro da fila, depois vai para 4 e assim por diante. O que podemos dizer sobre a ordem da fila de prioridade? Docs disse que os elementos da fila de prioridade são ordenados de acordo com sua ordem natural, ou por um Comparator fornecido no momento da construção da fila. No entanto, esta ordem não parece ser “natural” no significado de ordenação linear. Preferimos esperar [1, 2, 3, 4, 5], não [1, 2, 4, 5, 3]. Para entender por que a ordem de recuperação é assim, devemos nos lembrar daquela fila de prioridade baseada em um heap. Qual é a pilha? É uma estrutura de dados baseada em árvore binária. A principal propriedade do heap: a prioridade de cada pai é maior que as prioridades de seus filhos. Deixe-me lembrá-lo de que uma árvore é chamada de binário completo se cada pai não tiver mais de dois filhos e o preenchimento dos níveis for de cima para baixo (do mesmo nível - da esquerda para a direita). A pilha binária se reorganiza cada vez que elementos são adicionados ou removidos dela. No caso do min-heap, o menor elemento vai para a raiz independentemente da ordem de sua inserção. Fila de prioridade baseada neste heap mínimo. Isso significa que, no caso de elementos de fila de números, o primeiro elemento da fila será o mínimo desses números. Se você excluir a raiz, a próxima menor se tornará uma raiz.

Vamos voltar ao nosso exemplo.

Etapa 1. Colocamos '5' na fila de prioridade. Torna-se uma raiz. Etapa 2. Adicionamos '4' na fila de prioridade. 4 <5, então o novo elemento deve ser maior que o antigo. O 4 se torna uma raiz, 5 é seu filho esquerdo. Agora a estrutura de dados em Java é [4, 5] Etapa 3. Adicionamos '3'. Temporariamente torna-se um filho direito de uma raiz (4). No entanto, 3 < 4, então devemos levantá-lo. Troque 3 e 4. Agora temos uma estrutura como [3, 5, 4] Etapa 4. Adicionamos '2'. Torna-se um filho esquerdo de 5. 2<5, então troque-os. 2 torna-se um filho esquerdo de 3, 2 < 3, então mais um processo de troca. Agora temos uma estrutura [2,3,4,5] Passo 5.Nós adicionamos '1'. Vem do filho direito do 3 para o filho esquerdo do 2 e depois vai para a raiz. A estrutura de dados do resultado: [1,2,4,5,3] O processo de remoção começa a partir de uma raiz e provoca os procedimentos inversos. Então, primeiro temos 1 como raiz, depois 2, 3, 4 e por último 5. É por isso que usar a operação de remoção poll()

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

nós temos “classificados” na saída de sentido linear:

1
2
3
4
5

Portanto, a fila de prioridade pode ser eficaz para algumas operações. Leva tempo O(log N) para inserir e excluir cada elemento, e você pode obter o elemento mínimo em O(1). Aqui está o exemplo completo:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

É importante entender que as filas de prioridade são baseadas em heaps binários, portanto, não mantêm os elementos em ordem de classificação linear. Todos os caminhos da raiz até a folha são ordenados, mas os caminhos diferentes da raiz não. Isso significa que você pode obter o elemento mínimo da fila muito rapidamente.

O que você deve saber sobre a fila de prioridade. breve lista

• Priority Queue não permite objetos NULL.
• Você pode adicionar apenas objetos comparáveis ​​em PriorityQueue.
• A fila de prioridade é construída como um heap mínimo, uma espécie de árvore binária. O elemento mínimo é uma raiz. Os objetos da fila de prioridade são ordenados por padrão em ordem natural.
• Você pode usar o Comparator se precisar de ordenação personalizada.
• PriorityQueue não é thread-safe, então é melhor usar PriorityBlockingQueue para trabalhar em um ambiente simultâneo.
• PriorityQueue fornece tempo O(log(n)) para métodos add e poll e O(1) para obter elementos mínimos.