java - prioridad - ¿Cómo uso un PriorityQueue?

priority queue java example

Question

¿Cómo obtengo un PriorityQueue para ordenar en qué quiero que ordene?

Además, ¿hay alguna diferencia entre los métodos de offer y de add ?

Answer 1

Solución de Java 8

Podemos usar la lambda expression o la method reference introducida en Java 8. En caso de que tengamos algunos valores de cadena almacenados en la cola de prioridad, podemos proporcionar un comparador en línea (basado en la longitud de la cadena):

Usando la expresión lambda

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

Usando la referencia del 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 prioridad máxima) simplemente cambie el orden en el comparador en línea.

oferta () vs agregar ()

Según el doc

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 al lanzar una excepción no verificada. El método de oferta está diseñado para ser utilizado cuando la falla es una ocurrencia normal, en lugar de excepcional, por ejemplo, en colas de capacidad fija (o "limitada").

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

Answer 2

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

}

Answer 3

Como alternativa al uso de Comparator , también puede tener la clase que está usando en su Implementable de PriorityQueue Comparable (y, en consecuencia, anular el método compareTo ).

Tenga en cuenta que generalmente es mejor usar Comparable lugar de Comparator si ese orden es el ordenamiento intuitivo del objeto; si, por ejemplo, tiene un caso de uso para clasificar los objetos Person por edad, probablemente sea mejor usar solo 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;
    }
}

Salida:

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

Answer 4

No es diferente, como declara en javadoc:

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

Answer 5

Pásalo un Comparator . Rellene su tipo deseado en lugar de T

Usando lambdas (Java 8+):

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

De forma clásica, utilizando la 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 intercambie e1, e2.

Answer 6

Simplemente pase el Comparator apropiado al constructor :

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

La única diferencia entre offer y add es la interfaz a la que pertenecen. offer pertenece a Queue<E> , mientras que add se ve originalmente en la interfaz Collection<E> . Aparte de eso, ambos métodos hacen exactamente lo mismo: inserte el elemento especificado en la cola de prioridad.

Answer 7

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

De acuerdo con JavaDoc en la interfaz Queue , "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 en agregar un elemento solo al lanzar una excepción sin marcar. El método de oferta está diseñado para use cuando la falla es una ocurrencia 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 retorno agradable y bastante false , mientras que add() arroja una desagradable excepción no marcada que no desea en su código. Si no se puede agregar, el código funciona según lo previsto y / o es algo que verificará normalmente, utilice offer() . Si el hecho de no agregar significa que algo no funciona, use add() y maneje la excepción resultante según las especificaciones de la interfaz de la Colección .

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

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

Answer 8

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

Para una cola de prioridad:

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

Este codigo

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

puede imprimir de forma 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 de oferta () / add () solo insertan el elemento en la cola. Si desea un orden predecible, debe usar peek / poll que devuelve la cabeza. de la cola ".

Answer 9

Utilice la sobrecarga de constructor que toma un Comparator<? super E> comparator Comparator<? super E> comparator y pase un comparador que se compare de manera apropiada para su orden de clasificación. Si da un ejemplo de cómo desea ordenar, podemos proporcionar algunos ejemplos de código para implementar el comparador si no está seguro. (Aunque es bastante sencillo).

Como se ha dicho en otra parte: offer y add son solo implementaciones de métodos de interfaz diferentes. En la fuente JDK que tengo, add offer llamadas. Si bien la add y la offer tienen un comportamiento potencialmente diferente en general debido a la capacidad de la offer para indicar que el valor no puede agregarse debido a limitaciones de tamaño, esta diferencia es irrelevante en PriorityQueue que no tiene límites.

Aquí hay un ejemplo de una ordenación de colas de prioridad 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

de hecho muy largo

Answer 10

de la cola de la API :

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 al lanzar una excepción no verificada. El método de oferta está diseñado para ser utilizado cuando la falla es una ocurrencia normal, en lugar de excepcional, por ejemplo, en colas de capacidad fija (o "limitada").

Answer 11

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 que se asigne prioridad a cada uno de los elementos. Si no lo haces, Java lo hará por defecto. Al elemento con el menor valor se le asigna la prioridad más alta y, por lo tanto, primero se elimina de la cola. Si hay varios elementos con la misma prioridad más alta, el empate se rompe arbitrariamente. También puede especificar un orden utilizando 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 Comparador personalizado:

import java.util.Comparator;

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

Answer 12

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

Código abajo:

 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 añadir: link