Java PriorityQueue

PriorityQueue<E> é o heap do JDK. É uma Queue, mas em vez de FIFO, o topo é sempre o elemento menor de acordo com um Comparator (ou ordem natural, se você não fornecer um). offer é O(log n), poll e peek do topo são O(log n) e O(1) respectivamente, e o armazenamento subjacente é um array plano — sem alocação de nó por elemento. Isso o torna a ferramenta certa para problemas no estilo de escalonador: "trabalhe sempre no que for mais urgente a seguir."

O que significa "topo" aqui

Para uma fila FIFO, o topo é quem chegou primeiro. Para uma PriorityQueue, o topo é quem tem o menor valor naquele momento — não o menor no momento da inserção:

• peek() retorna o menor atual.
• poll() remove o menor atual e reequilibra; o próximo peek mostra o novo menor.
• offer(x) insere e reequilibra; se x for o novo menor, o próximo peek o retorna.

"Menor" é determinado por:

1. O Comparator que você passou ao construtor, se houver.
2. Caso contrário, a ordem natural do elemento via Comparable. Se seus elementos não forem Comparable e você não passou um Comparator, a primeira chamada que precisar comparar lança ClassCastException.

Não há modo de heap máximo. Se você quiser um max-heap, passe Comparator.reverseOrder() (ou seu comparador personalizado revertido) — esse é o idioma padrão e usamos no exemplo abaixo.

Construindo uma

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

O construtor de argumento único que recebe uma Collection é O(n) — ele realiza o heapify em massa em vez de n offers O(log n). Útil quando você já tem todos os dados desde o início.

Iteração NÃO está em ordem de prioridade

Essa é a surpresa que a maioria das pessoas encontra uma vez. Iterar uma PriorityQueue percorre o array do heap subjacente na ordem em que o heap armazena seus nós — não em ordem crescente:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + " "); // possibly: 10 20 30 40
                                            // possibly: 10 40 30 20

A ordem de impressão é um detalhe de implementação do layout do heap. Se você quiser os elementos em ordem de prioridade, precisa esvaziar:

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // sorted

Fique atento a isso quando usar forEach, stream, toArray ou simplesmente imprimir a fila para depuração. O Stream retornado por stream() não está ordenado, e adicionar .sorted() a ele requer que os elementos sejam Comparable (ou você pode passar um comparador).

Mutar um elemento após offer quebra o heap

A prioridade é calculada no momento da inserção. Se você colocar um elemento e depois mutar o campo que o comparador observa, o heap estará em estado inválido — poll pode retornar o topo errado, contains pode falhar, você perde o invariante. Não existe método update ou decrease-key.

As duas alternativas:

• Use elementos imutáveis — records com campos de prioridade, ou records de wrapper como record Task(int priority, String name) {}. Assim não há nada a mutar após a inserção.
• Remova e reinsira se você realmente precisar mudar a prioridade: pq.remove(task) é O(n) (busca linear), depois pq.offer(taskWithNewPriority) é O(log n).

Para uma fila pequena, remover e reinserir está ótimo. Para "estou reimplementando o algoritmo de Dijkstra e preciso de decrease-key rápido", uma PriorityQueue não é a ferramenta certa — você quer um heap indexado ou um TreeSet de pares (prioridade, nó).

null e segurança de thread

As mesmas regras do restante de Queue:

• Sem nulos. pq.offer(null) lança NullPointerException.
• Não é thread-safe. Acesso concorrente precisa de PriorityBlockingQueue, o equivalente em java.util.concurrent.

Um exemplo prático: um mini escalonador de tarefas

O programa abaixo usa uma PriorityQueue para escalonar tarefas por prioridade (número menor = mais urgente). Ele também mostra o idioma de max-heap e a surpresa da ordem de iteração.

Lendo a execução:

• toString() e forEach mostraram as tarefas em alguma ordem — não ordenada. Não use nenhum dos dois para depurar "a prioridade está correta?" — esvazie com poll para ver a ordem real.
• O construtor em massa produziu um heap corretamente ordenado de uma vez — esse é o caminho de heapify em tempo linear.
• O bloco de mutação no final é a armadilha na forma concentrada. Mutamos a prioridade do array após oferecê-lo, o heap não teve chance de reequilibrar, e agora peek está mentindo. A correção é usar um wrapper imutável ou fazer remove-e-offer após a mudança.

O que vem a seguir

O próximo capítulo aborda a implementação que você usa quando quer uma fila FIFO ou uma pilha ou um deque — e a que o Javadoc do JDK recomenda como padrão para os três: ArrayDeque. É a classe que faz a maior parte do trabalho nos bastidores no código de exemplo dos dois capítulos anteriores.

Prática