Como uso um PriorityQueue?

Como faço PriorityQueuepara classificar o que eu quero?

Além disso, existe uma diferença entre os métodos offere add?

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

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.

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.

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").

não é diferente, como declara em javadoc:

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

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.

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

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.

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 ".

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

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
    }
}

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

}