Como eu uso um PriorityQueue?

Como obtenho um PriorityQueue para classificar o que eu quero classificar?

Além disso, existe uma diferença entre a offer e os methods add ?

Use o construtor de sobrecarga que leva um Comparator< ? super E> comparator Comparator< ? super E> comparator e passar em um comparador que compara da maneira apropriada para sua ordem de sorting. Se você der um exemplo de como deseja classificar, podemos fornecer um código de exemplo para implementar o comparador, caso não tenha certeza. (É bastante simples embora.)

Como já foi dito em outro lugar: offer e add são apenas implementações de methods de interface diferentes. Na fonte do JDK que eu tenho, add chamadas de offer . Embora a add e a offer tenham um comportamento potencialmente diferente em geral, devido à capacidade da offer de indicar que o valor não pode ser adicionado devido a limitações de tamanho, essa diferença é irrelevante no PriorityQueue que é ilimitado.

Aqui está um exemplo de uma fila de prioridade de sorting por comprimento de cadeia:

 // Test.java import java.util.Comparator; import java.util.PriorityQueue; public class Test { public static void main(String[] args) { Comparator comparator = new StringLengthComparator(); PriorityQueue queue = new PriorityQueue(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 { @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:

curto

médio

muito longo mesmo

Solução Java 8

Podemos usar a lambda expression ou a method reference introduzida no Java 8. No caso de termos alguns valores String armazenados na fila de prioridade, podemos fornecer um comparador embutido (com base no tamanho da string):

Usando expressão lambda

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

Usando referência de método

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

Então podemos usar qualquer um deles como:

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

Isto irá imprimir:

 Apple PineApple Custard Apple 

Para inverter a ordem (para alterá-la para a fila de prioridade máxima), basta alterar a ordem no comparador embutido.

offer () vs add ()

De acordo com o documento

O método de oferta insere um elemento, se possível, caso contrário, retorna 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 é projetado para uso quando a falha é uma ocorrência normal, em vez de excepcional, por exemplo, em filas de capacidade fixa (ou “limitadas”).

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

Basta passar o Comparator apropriado ao construtor :

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

A única diferença entre offer e add é a interface a que pertencem. offer pertence ao Queue , enquanto add é originalmente visto na interface Collection . Além de que ambos os methods fazem exatamente a mesma coisa – insira o elemento especificado na fila de prioridade.

da API da fila :

O método de oferta insere um elemento, se possível, caso contrário, retorna 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 é projetado para uso quando a falha é uma ocorrência normal, em vez de excepcional, por exemplo, em filas de capacidade fixa (ou “limitadas”).

não é diferente, como declara no javadoc:

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

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

De acordo com o JavaDoc na interface Queue , “O método de oferta insere um elemento, se possível, caso contrário, retorna 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 é projetado para use quando a falha é uma ocorrência normal, em vez de excepcional, por exemplo, em filas de capacidade fixa (ou “limitadas”). ”

Isso significa que, se você puder adicionar o elemento (que sempre deve ser o caso em um PriorityQueue), eles funcionarão exatamente da mesma maneira. Mas se você não puder adicionar o elemento, o offer() lhe dará um retorno bonito e false , enquanto o add() lançará uma desagradável exceção não checada que você não quer no seu código. Se a falha em adicionar significa que o código está funcionando conforme o esperado e / ou é algo que você verificará normalmente, use offer() . Se a falha em adicionar 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 desta forma para preencher o contrato na interface Queue que especifica offer() falha ao retornar um false ( método preferencial em filas de capacidade restrita ) e também mantém o contrato na interface Collection que especifica add() sempre falha por jogando uma exceção .

De qualquer forma, espero que esclarece pelo menos essa parte da questão.

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

Abaixo do código:

  import java.util.*; import java.util.Collections; import java.util.Comparator; class Checker implements Comparator { 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 queue=new PriorityQueue(5, new Checker()); queue.add("india"); queue.add("bangladesh"); queue.add("pakistan"); while (queue.size() != 0) { System.out.printf("%s\n",queue.remove()); } } } 

Saída:

  india pakistan bangladesh 

Diferença entre a oferta e os methods add: link

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

Para uma fila de prioridades:

 PriorityQueue pq3 = new PriorityQueue(); 

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); 

Eu encontrei a resposta de uma discussão em outro fórum , onde um usuário disse, “os methods offer () / add () apenas inserem o elemento na fila. Se você quer uma ordem previsível você deve usar o peek / poll que retorna a cabeça da fila “.

Como uma alternativa ao uso do Comparator , você também pode ter a class que está usando no seu implemento de PriorityQueue Comparable (e, correspondentemente, replace o método compareTo ).

Observe que geralmente é melhor usar Comparable vez de Comparator se essa ordenação for a ordenação intuitiva do object – se, por exemplo, você tiver um caso de uso para classificar objects Person por idade, provavelmente será melhor usar apenas Comparator .

 import java.lang.Comparable; import java.util.PriorityQueue; class Test { public static void main(String[] args) { PriorityQueue queue = new PriorityQueue(); 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 { 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; } } 

Saída:

 1, short 1, medium 1, very long indeed 2, short 2, medium 2, very long indeed 

Fila de prioridade tem alguma prioridade atribuída a cada elemento, o elemento com prioridade mais alta aparece no topo da fila. Agora, depende de você como você deseja prioridade atribuída a cada um dos elementos. Se você não fizer isso, 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)

Exemplo de código:

 PriorityQueue 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 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() + " "); } 

Saída:

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

Além disso, você também pode definir o comparador personalizado:

 import java.util.Comparator; public class StringLengthComparator implements Comparator { @Override public int compare(String x, String y) { //Your Own Logic } } 

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 cpq = new PriorityQueue<>(7, idComp); addToQueue(cpq); pollFromQueue(cpq); } public static Comparator idComp = new Comparator(){ @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 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 cq){ while(true){ Customer c = cq.poll(); if(c == null) break; System.out.println("Customer Polled : "+c.getId() + " "+ c.getName()); } } } 

Passe um Comparator . Preencha o seu tipo desejado no lugar de T

Usando lambdas (Java 8+):

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

Forma clássica, usando a class anônima:

 int initialCapacity = 10; PriorityQueue pq = new PriorityQueue<>(initialCapacity, new Comparator () { @Override public int compare(T e1, T e2) { return e1.compareTo(e2); } }); 

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