Jak korzystać z PriorityQueue?

Jak uzyskać PriorityQueuesortowanie według tego, na czym chcę sortować?

Czy istnieje różnica między metodami offera add?

Użyj przeciążenia konstruktora, które pobiera Comparator<? super E> comparatori przekazuje komparator, który porównuje w odpowiedni sposób dla twojej kolejności sortowania. Jeśli podasz przykładowy sposób sortowania, możemy podać przykładowy kod do implementacji komparatora, jeśli nie jesteś pewien. (Jest to jednak dość proste.)

Jak już zostało powiedziane w innym miejscu: offeri addsą po prostu różne implementacje metody interfejsu. W źródle JDK, które mam, addpołączenia offer. Chociaż addi ogólnie offermają potencjalnie różne zachowanie ze względu na możliwość offerwskazania, że ​​wartości nie można dodać z powodu ograniczeń wielkości, różnica ta nie ma znaczenia, dla PriorityQueuektórej nie ma ograniczeń.

Oto przykład sortowania kolejki priorytetowej według długości łańcucha:

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

Oto wynik:

krótki

średni

naprawdę bardzo długo

Rozwiązanie Java 8

Możemy używać lambda expressionlub method referencewprowadzać w Javie 8. W przypadku, gdy mamy pewne wartości String zapisane w kolejce priorytetowej (o pojemności 5), możemy zapewnić wbudowany komparator (na podstawie długości String):

Korzystanie z wyrażenia lambda

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

Za pomocą odwołania do metody

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

Następnie możemy użyć dowolnego z nich jako:

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

Spowoduje to wydrukowanie:

Apple
PineApple
Custard Apple

Aby odwrócić kolejność (aby zmienić na kolejkę o najwyższym priorytecie), wystarczy zmienić kolejność w komparatorze wbudowanym lub użyć reversedjako:

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

Możemy również użyć Collections.reverseOrder:

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

Widzimy więc, że Collections.reverseOrderjest przeciążony, aby wziąć komparator, który może być przydatny dla obiektów niestandardowych. Te reversedrzeczywiście wykorzystuje Collections.reverseOrder:

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

offer () vs add ()

Zgodnie z dok

Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona do użycia, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”).

W przypadku korzystania z kolejki o ograniczonej pojemności opcja () jest na ogół lepsza niż metoda add (), która może nie wstawić elementu tylko przez zgłoszenie wyjątku. A PriorityQueue to nieograniczona kolejka priorytetowa oparta na stercie priorytetów.

Wystarczy zaliczyć odpowiednie Comparatordo konstruktora :

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

Jedyną różnicą między offeri addjest interfejs, do którego należą. offernależy do Queue<E>, podczas gdy addpierwotnie jest widoczny w Collection<E>interfejsie. Poza tym obie metody robią dokładnie to samo - wstawiają określony element do kolejki priorytetowej.

z interfejsu API kolejki :

Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona do użycia, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”).

nie inaczej, jak deklarują w javadoc:

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

Wystarczy odpowiedzieć na pytanie add()vs offer()(ponieważ na drugie pytanie jest doskonale udzielone imo, a może nie być):

Według JavaDoc w interfejsie kolejki : „Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona dla używaj, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”). ”

Oznacza to, że jeśli możesz dodać element (co powinno zawsze mieć miejsce w przypadku PriorityQueue), działają one dokładnie tak samo. Ale jeśli nie możesz dodać elementu, offer()da ci ładny i ładny falsezwrot, a add()zgłasza nieprzyjemny wyjątek, którego nie chcesz w swoim kodzie. Jeśli brak dodania oznacza, że ​​kod działa zgodnie z przeznaczeniem i / lub sprawdzasz go normalnie, użyj offer(). Jeśli brak dodawania oznacza, że ​​coś jest zepsute, użyj add()i obsłuż wynikowy wyjątek zgłoszony zgodnie ze specyfikacjami interfejsu kolekcji .

Oba są zaimplementowane w ten sposób, aby wypełnić kontrakt na interfejsie kolejki, który określa offer()awarie poprzez zwrócenie false( metoda preferowana w kolejkach o ograniczonej pojemności ), a także utrzymać kontrakt na interfejsie kolekcji, który określa,add() że zawsze kończy się niepowodzeniem przez zgłoszenie wyjątku .

W każdym razie, mam nadzieję, że wyjaśni to przynajmniej tę część pytania.

Tutaj możemy zdefiniować komparator zdefiniowany przez użytkownika:

Poniżej kodu:

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

Wynik :

   india                                               
   pakistan                                         
   bangladesh

Różnica między ofertą a metodami dodawania: link

Podaj to Comparator. Wpisz żądany typ zamiastT

Korzystanie z lambdas (Java 8+):

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

Klasyczny sposób, z wykorzystaniem anonimowej klasy:

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

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

});

Aby posortować w odwrotnej kolejności, po prostu zamień e1, e2.

Zastanawiałem się także nad kolejnością drukowania. Rozważ ten przypadek, na przykład:

W przypadku kolejki priorytetowej:

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

Ten kod:

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

może drukować inaczej niż:

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

Znalazłem odpowiedź z dyskusji na innym forum , na której użytkownik powiedział: „metody offer () / add () wstawiają tylko element do kolejki. Jeśli chcesz przewidzieć kolejność, powinieneś użyć peek / poll, które zwracają głowę w kolejce. ”

Alternatywą dla użycia Comparatormoże być także klasa, której używasz w swoim PriorityQueue narzędziuComparable (i odpowiednio przesłonić compareTometodę).

Zauważ, że generalnie najlepiej jest używać Comparablezamiast tego, Comparatorjeśli porządkowanie jest intuicyjne porządkowanie obiektu - jeśli na przykład masz przypadek użycia do sortowania Personobiektów według wieku, prawdopodobnie najlepiej po prostu użyć Comparatorzamiast tego.

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

Wynik:

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

Kolejka priorytetowa ma pewien priorytet przypisany do każdego elementu. Element o najwyższym priorytecie pojawia się na początku kolejki. Teraz zależy od Ciebie, w jaki sposób chcesz przypisać priorytet każdemu z elementów. Jeśli tego nie zrobisz, Java zrobi to domyślnie. Element o najmniejszej wartości ma najwyższy priorytet i dlatego jest najpierw usuwany z kolejki. Jeśli jest kilka elementów o tym samym najwyższym priorytecie, remis zostaje zerwany arbitralnie. Możesz także określić kolejność za pomocą Komparatora w konstruktorze PriorityQueue(initialCapacity, comparator)

Przykładowy kod:

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

Wynik:

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

W przeciwnym razie możesz także zdefiniować własny komparator:

import java.util.Comparator;

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

Oto prosty przykład, którego możesz użyć do wstępnej nauki:

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

}