Como uso um PriorityQueue?

Respostas:

449

Use a sobrecarga do construtor que recebe Comparator<? super E> comparatore passa em um comparador que compara da maneira apropriada para sua ordem de classificação. Se você der um exemplo de como deseja classificar, podemos fornecer alguns exemplos de código para implementar o comparador, se você não tiver certeza. (É bastante simples.)

Como foi dito em outro lugar: offere addsão apenas implementações diferentes de métodos de interface. Na fonte JDK que tenho, addchama offer. Embora adde offerpossua um comportamento potencialmente diferente em geral devido à capacidade de offerindicar que o valor não pode ser adicionado devido a limitações de tamanho, essa diferença é irrelevante na PriorityQueuequal é ilimitada.

Aqui está um exemplo de uma fila de prioridade que classifica pelo comprimento da string:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Aqui está a saída:

baixo

médio

muito tempo mesmo

Jon Skeet
fonte
7
Hmm ... acabei de notar ... priorityQueue.comparator () "Retorna o comparador usado para ordenar esta coleção ou nulo se essa coleção for classificada de acordo com a ordenação natural de seus elementos (usando Comparable)." Isso significa que eu também poderia implementar o Comparable na minha classe?
Svish
7
Você poderia sim. Eu não faria isso, a menos que exista uma única ordem de classificação natural para sua classe. Se houver, isso é a coisa certa a fazer :)
Jon Skeet
8
A compareimplementação não deveria ser apenas return x.length() - y.length()? (Predição ramo Evita)
Franky
7
@Franky: Poderia ser, sim - embora eu diria que é um pouco mais difícil de entender, e o objetivo da resposta é demonstrar como funciona. Vou adicionar um comentário.
Jon Skeet
2
@KarelG: Eu não acho que isso importe muito, desde que você esteja ciente das diferenças. Eu acho que se você estiver usando add()a operação de adição, será remove()sensato; se eu estivesse usando offer(), provavelmente usaria poll()... mas isso é apenas uma preferência pessoal.
Jon Skeet
68

Solução Java 8

Podemos usar lambda expressionou method referenceintroduzir no Java 8. Caso tenhamos alguns valores de String armazenados na fila de prioridade (com capacidade 5), podemos fornecer um comparador em linha (com base no comprimento de String):

Usando expressão lambda

PriorityQueue<String> pq=
                    new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

Usando referência de método

PriorityQueue<String> pq=
                new PriorityQueue<String>(5, Comparator.comparing(String::length));

Em seguida, podemos usar qualquer um deles como:

public static void main(String[] args) {
        PriorityQueue<String> pq=
                new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
       // or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
        pq.add("Apple");
        pq.add("PineApple");
        pq.add("Custard Apple");
        while (pq.size() != 0)
        {
            System.out.println(pq.remove());
        }
    }

Isso imprimirá:

Apple
PineApple
Custard Apple

Para reverter a ordem (para alterá-la para a fila de prioridade máxima), basta alterar a ordem no comparador embutido ou usar reversedcomo:

PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                             Comparator.comparing(String::length).reversed());

Também podemos usar Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                Collections.reverseOrder(Comparator.comparing(String::length))

Portanto, podemos ver que Collections.reverseOrderestá sobrecarregado para levar o comparador, que pode ser útil para objetos personalizados. O reversedrealmente usa Collections.reverseOrder:

default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
}

offer () vs add ()

De acordo com o documento

O método de oferta insere um elemento, se possível, retornando false. Isso difere do método Collection.add, que pode falhar ao adicionar um elemento apenas lançando uma exceção não verificada. O método de oferta foi projetado para uso quando a falha é uma ocorrência normal, e não excepcional, por exemplo, em filas de capacidade fixa (ou "limitada").

Ao usar uma fila com capacidade restrita, geralmente é preferível offer () adicionar (), que pode falhar ao inserir um elemento apenas lançando uma exceção. E PriorityQueue é uma fila de prioridade ilimitada com base em um heap de prioridade.

akhil_mittal
fonte
Estou assumindo que 5indica a capacidade inicial da fila?
Neil
11
@Neil Sim, eu fiz isso mais explícito na resposta agora :)
akhil_mittal
11
A 8ª versão do Java foi a melhor coisa que já aconteceu com a linguagem
GabrielBB 13/06/19
11
Explicação muito boa com exemplo lúcido.
Vishwa Ratna
24

Apenas passe apropriado Comparatorpara o construtor :

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

A única diferença entre offere addé a interface à qual eles pertencem. offerpertence a Queue<E>, enquanto que addé originalmente visto na Collection<E>interface. Além disso, os dois métodos fazem exatamente a mesma coisa - insira o elemento especificado na fila de prioridade.

libélula
fonte
7
Especificamente, add () lança uma exceção se restrições de capacidade impedirem que o item seja adicionado à fila, enquanto a oferta retorna false. Como PriorityQueues não tem capacidade máxima, a diferença é discutível.
James
Essa é uma distinção muito clara entre add () e offer (). E add () era necessário para ser implementado de qualquer maneira!
whitehat
19

da API da fila :

O método de oferta insere um elemento, se possível, retornando false. Isso difere do método Collection.add, que pode falhar ao adicionar um elemento apenas lançando uma exceção não verificada. O método de oferta foi projetado para uso quando a falha é uma ocorrência normal, e não excepcional, por exemplo, em filas de capacidade fixa (ou "limitada").

Pedro
fonte
12

não é diferente, como declara em javadoc:

public boolean add(E e) {
    return offer(e);
}
d1ck50n
fonte
6

Apenas para responder à pergunta add()vs offer()(já que a outra é perfeitamente respondida imo, e isso pode não ser):

De acordo com JavaDoc na interface Queue , "O método offer insere um elemento, se possível, retornando false. Isso difere do método Collection.add, que pode falhar ao adicionar um elemento apenas lançando uma exceção não verificada. O método offer foi projetado para use quando a falha for uma ocorrência normal, e não excepcional, por exemplo, em filas de capacidade fixa (ou "limitada") ".

Isso significa que, se você pode adicionar o elemento (que sempre deve ser o caso em um PriorityQueue), eles funcionam exatamente da mesma maneira. Mas se você não pode adicionar o elemento, offer()ele fornecerá um falseretorno agradável e bonito , enquanto add()lança uma exceção desagradável e desmarcada, que você não deseja no seu código. Se a falha ao adicionar significa que o código está funcionando como pretendido e / ou é algo que você verificará normalmente, use offer(). Se a falha na adição significar que algo está quebrado, use add()e manipule a exceção resultante lançada de acordo com as especificações da interface Collection .

Ambos são implementados dessa maneira para preencher o contrato na interface da Fila que especifica offer()falhas retornando um false( método preferencial em filas com capacidade restrita ) e também mantêm o contrato na interface de Coleta que especifica add()sempre falhas ao lançar uma exceção .

Enfim, espero que isso esclareça pelo menos essa parte da questão.

Blueriver
fonte
6

Aqui, podemos definir o comparador definido pelo usuário:

Abaixo código:

 import java.util.*;
 import java.util.Collections;
 import java.util.Comparator; 


 class Checker implements Comparator<String>
 {
    public int compare(String str1, String str2)
    {
        if (str1.length() < str2.length()) return -1;
        else                               return 1;
    }
 }


class Main
{  
   public static void main(String args[])
    {  
      PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());  
      queue.add("india");  
      queue.add("bangladesh");  
      queue.add("pakistan");  

      while (queue.size() != 0)
      {
         System.out.printf("%s\n",queue.remove());
      }
   }  
}  

Resultado :

   india                                               
   pakistan                                         
   bangladesh

Diferença entre os métodos de oferta e adição: link

rashedcs
fonte
11
e se eles são iguais.
Nycynik 22/04/19
4

Passe um Comparator. Preencha o tipo desejado no lugar deT

Usando lambdas (Java 8+):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

Maneira clássica, usando classe anônima:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {

    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }

});

Para ordenar na ordem inversa, basta trocar e1, e2.

James Wierzba
fonte
3

Eu também estava pensando sobre a ordem de impressão. Considere este caso, por exemplo:

Para uma fila de prioridade:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

Este código:

pq3.offer("a");
pq3.offer("A");

pode imprimir de maneira diferente de:

String[] sa = {"a", "A"}; 
for(String s : sa)   
   pq3.offer(s);

Encontrei a resposta de uma discussão em outro fórum , em que um usuário disse: "os métodos offer () / add () inserem apenas o elemento na fila. Se você deseja uma ordem previsível, deve usar o peek / poll que retorna a cabeça da fila ".

joserey
fonte
3

Como alternativa ao uso Comparator, você também pode ter a classe que está usando no seu PriorityQueue implementoComparable (e, sobrescrever, substituir o compareTométodo).

Observe que geralmente é melhor usar apenas em Comparablevez de Comparatorse essa ordem for a ordem intuitiva do objeto - se, por exemplo, você tiver um caso de uso para classificar Personobjetos por idade, provavelmente é melhor usar apenas Comparator.

import java.lang.Comparable;
import java.util.PriorityQueue;

class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
        queue.add(new MyClass(2, "short"));
        queue.add(new MyClass(2, "very long indeed"));
        queue.add(new MyClass(1, "medium"));
        queue.add(new MyClass(1, "very long indeed"));
        queue.add(new MyClass(2, "medium"));
        queue.add(new MyClass(1, "short"));
        while (queue.size() != 0)
            System.out.println(queue.remove());
    }
}
class MyClass implements Comparable<MyClass>
{
    int sortFirst;
    String sortByLength;

    public MyClass(int sortFirst, String sortByLength)
    {
        this.sortFirst = sortFirst;
        this.sortByLength = sortByLength;
    }

    @Override
    public int compareTo(MyClass other)
    {
        if (sortFirst != other.sortFirst)
            return Integer.compare(sortFirst, other.sortFirst);
        else
            return Integer.compare(sortByLength.length(), other.sortByLength.length());
    }

    public String toString()
    {
        return sortFirst + ", " + sortByLength;
    }
}

Resultado:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed
Bernhard Barker
fonte
1

A fila de prioridade tem alguma prioridade atribuída a cada elemento. O elemento com maior prioridade aparece na parte superior da fila. Agora, depende de você como você deseja que a prioridade seja atribuída a cada um dos elementos. Caso contrário, o Java fará isso da maneira padrão. O elemento com o menor valor recebe a prioridade mais alta e, portanto, é removido da fila primeiro. Se houver vários elementos com a mesma prioridade mais alta, o empate será quebrado arbitrariamente. Você também pode especificar uma ordem usando o Comparator no construtor PriorityQueue(initialCapacity, comparator)

Código de exemplo:

PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
    System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
    System.out.print(queue2.remove() + " ");
}

Resultado:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas 
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia 

Senão, você também pode definir o Comparador Personalizado:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String>
{
    @Override
    public int compare(String x, String y)
    {
        //Your Own Logic
    }
}
devDeejay
fonte
1

Aqui está o exemplo simples que você pode usar para o aprendizado inicial:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PQExample {

    public static void main(String[] args) {
        //PriorityQueue with Comparator
        Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
        addToQueue(cpq);
        pollFromQueue(cpq);
    }

    public static Comparator<Customer> idComp = new Comparator<Customer>(){

        @Override
        public int compare(Customer o1, Customer o2) {
            return (int) (o1.getId() - o2.getId());
        }

    };

    //utility method to add random data to Queue
    private static void addToQueue(Queue<Customer> cq){
        Random rand = new Random();
        for(int i=0;i<7;i++){
            int id = rand.nextInt(100);
            cq.add(new Customer(id, "KV"+id));
        }
    }


    private static void pollFromQueue(Queue<Customer> cq){
        while(true){
            Customer c = cq.poll();
            if(c == null) break;
            System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
        }
    }

}
KayV
fonte