¿Cómo uso un PriorityQueue?

¿Cómo obtengo un PriorityQueueorden sobre lo que quiero que clasifique?

Además, ¿hay alguna diferencia entre los métodos offery add?

Use la sobrecarga del constructor que toma ay Comparator<? super E> comparatorpase en un comparador que se compara de la manera apropiada para su orden de clasificación. Si da un ejemplo de cómo desea ordenar, podemos proporcionar un código de muestra para implementar el comparador si no está seguro. (Sin embargo, es bastante sencillo).

Como se ha dicho en otra parte: offery addson solo implementaciones de métodos de interfaz diferentes. En la fuente JDK que tengo, addllamadas offer. Aunque addy offertienen un comportamiento potencialmente diferente en general debido a la capacidad de offerindicar que el valor no se puede agregar debido a limitaciones de tamaño, esta diferencia es irrelevante en lo PriorityQueueque no tiene límites.

Aquí hay un ejemplo de una clasificación de cola prioritaria por longitud de cadena:

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

Aquí está la salida:

corto

medio

muy largo de hecho

Solución Java 8

Podemos usar lambda expressiono method referenceintroducir en Java 8. En caso de que tengamos algunos valores de String almacenados en la Cola de prioridad (con capacidad 5), podemos proporcionar un comparador en línea (basado en la longitud de String):

Usando la expresión lambda

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

Usando referencia de método

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

Entonces podemos usar cualquiera de ellos 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());
        }
    }

Esto imprimirá:

Apple
PineApple
Custard Apple

Para invertir el orden (para cambiarlo a la cola de máxima prioridad) simplemente cambie el orden en el comparador en línea o úselo reversedcomo:

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

También 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))

Entonces podemos ver que Collections.reverseOrderestá sobrecargado para tomar el comparador que puede ser útil para objetos personalizados. El reversedrealmente utiliza Collections.reverseOrder:

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

oferta () vs agregar ()

Según el documento

El método de oferta inserta un elemento si es posible, de lo contrario devuelve falso. Esto difiere del método Collection.add, que puede fallar al agregar un elemento solo lanzando una excepción no verificada. El método de oferta está diseñado para usarse cuando la falla es una ocurrencia normal, en lugar de excepcional, por ejemplo, en colas de capacidad fija (o "limitada").

Cuando se usa una cola de capacidad restringida, generalmente es preferible ofrecer () a add (), que puede fallar al insertar un elemento solo lanzando una excepción. Y PriorityQueue es una cola de prioridad ilimitada basada en un montón de prioridad.

Simplemente pase apropiado Comparatoral constructor :

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

La única diferencia entre offery addes la interfaz a la que pertenecen. offerpertenece a Queue<E>, mientras addque originalmente se ve en la Collection<E>interfaz. Aparte de eso, ambos métodos hacen exactamente lo mismo: insertar el elemento especificado en la cola de prioridad.

de la API de cola :

El método de oferta inserta un elemento si es posible, de lo contrario devuelve falso. Esto difiere del método Collection.add, que puede fallar al agregar un elemento solo lanzando una excepción no verificada. El método de oferta está diseñado para usarse cuando la falla es una ocurrencia normal, en lugar de excepcional, por ejemplo, en colas de capacidad fija (o "limitada").

no es diferente, como declaramos en javadoc:

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

Solo para responder la pregunta add()vs offer()(ya que la otra está perfectamente respondida imo, y esto podría no ser así):

De acuerdo con JavaDoc en la cola de la interfaz , "El método de oferta inserta un elemento si es posible, de lo contrario devuelve falso. Esto difiere del método Collection.add, que puede fallar al agregar un elemento solo lanzando una excepción no verificada. El método de oferta está diseñado para se usa cuando la falla es normal, en lugar de excepcional, por ejemplo, en colas de capacidad fija (o "limitada").

Eso significa que si puede agregar el elemento (que siempre debería ser el caso en un PriorityQueue), funcionan exactamente igual. Pero si no puede agregar el elemento, offer()le dará un falseretorno agradable y bonito , mientras add()arroja una desagradable excepción no marcada que no desea en su código. Si la falta de agregar significa que el código funciona según lo previsto y / o es algo que verificará normalmente, úselo offer(). Si la falta de agregar significa que algo está roto, use add()y maneje la excepción resultante lanzada de acuerdo con las especificaciones de la interfaz de la Colección .

Ambos se implementan de esta manera para completar el contrato en la interfaz de cola que especifica offer()fallas al devolver un false( método preferido en colas de capacidad restringida ) y también mantener el contrato en la interfaz de colección que especifica add()siempre falla lanzando una excepción .

De todos modos, espero que eso aclare al menos esa parte de la pregunta.

Aquí, podemos definir un comparador definido por el usuario:

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

Salida:

   india                                               
   pakistan                                         
   bangladesh

Diferencia entre la oferta y los métodos de agregar: enlace

Pásalo a Comparator. Complete el tipo deseado en lugar deT

Usando lambdas (Java 8+):

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

Manera clásica, usando clase 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 en orden inverso, simplemente cambie e1, e2.

También me preguntaba sobre la orden de impresión. Considere este caso, por ejemplo:

Para una cola prioritaria:

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

Este código:

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

puede imprimir de manera diferente a:

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

Encontré la respuesta de una discusión en otro foro , donde un usuario dijo: "los métodos offer () / add () solo insertan el elemento en la cola. Si desea un orden predecible, debe usar peek / poll que devuelve el encabezado de la cola ".

Como alternativa al uso Comparator, también puede tener la clase que está usando en su PriorityQueue implementoComparable (y anular la correspondientecompareTo método ).

Tenga en cuenta que generalmente es mejor usar solo en Comparablelugar de Comparatorsi ese orden es el ordenamiento intuitivo del objeto; si, por ejemplo, tiene un caso de uso para ordenar Personobjetos por edad, probablemente sea mejor usarlo Comparatoren su lugar.

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

Salida:

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

La cola de prioridad tiene alguna prioridad asignada a cada elemento. El elemento con la prioridad más alta aparece en la parte superior de la cola. Ahora, depende de usted cómo desea asignar la prioridad a cada uno de los elementos. Si no lo hace, Java lo hará de la manera predeterminada. Al elemento con el menor valor se le asigna la máxima prioridad y, por lo tanto, se elimina primero de la cola. Si hay varios elementos con la misma prioridad más alta, el empate se rompe arbitrariamente. También puede especificar un pedido usando Comparator en el constructor PriorityQueue(initialCapacity, comparator)

Código de ejemplo:

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

Salida:

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

De lo contrario, también puede definir un comparador personalizado:

import java.util.Comparator;

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

Aquí está el ejemplo simple que puede usar para el aprendizaje 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());
        }
    }

}