Wie verwende ich eine PriorityQueue?

Question

Wie bekomme ich eine PriorityQueue nach dem zu sortieren, was ich möchte?

Gibt es außerdem einen Unterschied zwischen dem offer y add Methoden?

Answer 1

Verwenden Sie die Überladung des Konstruktors, der eine Comparator<? super E> comparator und geben Sie einen Komparator ein, der in der für Ihre Sortierreihenfolge geeigneten Weise vergleicht. Wenn Sie uns ein Beispiel dafür geben, wie Sie sortieren möchten, können wir Ihnen einen Beispielcode zur Implementierung des Komparators zur Verfügung stellen, wenn Sie sich nicht sicher sind. (Es ist allerdings ziemlich einfach.)

Wie bereits an anderer Stelle gesagt wurde: offer y add sind lediglich unterschiedliche Implementierungen von Schnittstellenmethoden. In der JDK-Quelle, die ich habe, add ruft auf. offer . Obwohl add y offer haben Möglicherweise ein anderes Verhalten im Allgemeinen aufgrund der Fähigkeit zur offer um anzuzeigen, dass der Wert aufgrund von Größenbeschränkungen nicht hinzugefügt werden kann, ist dieser Unterschied in PriorityQueue die nicht begrenzt ist.

Hier ein Beispiel für eine Prioritätswarteschlange, die nach der Länge der Zeichenkette sortiert ist:

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

Hier ist die Ausgabe:

kurz

mittel

in der Tat sehr lang

Answer 2

Java 8 Lösung

Wir können verwenden lambda expression ou method reference die in Java 8 eingeführt wurde. Für den Fall, dass wir einige String-Werte in der Prioritäts-Warteschlange (mit Kapazität 5) gespeichert haben, können wir einen Inline-Vergleicher (basierend auf der Länge des Strings) bereitstellen:

Lambda-Ausdruck verwenden

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

Verwendung der Methodenreferenz

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

Dann können wir jeden von ihnen als verwenden:

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

Dies wird gedruckt:

Apple
PineApple
Custard Apple

Um die Reihenfolge umzukehren (auf eine Warteschlange mit maximaler Priorität umzustellen), ändern Sie einfach die Reihenfolge im Inline-Komparator oder verwenden Sie reversed als:

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

Wir können auch verwenden Collections.reverseOrder :

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

Wir können also feststellen, dass Collections.reverseOrder ist überladen, um Komparator zu nehmen, was für benutzerdefinierte Objekte nützlich sein kann. Der reversed verwendet tatsächlich Collections.reverseOrder :

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

anbieten() vs. hinzufügen()

Gemäß der doc

Die Methode offer fügt ein Element ein, wenn dies möglich ist, andernfalls gibt sie falsch zurück. Dies unterscheidet sich von der Methode Collection.add, bei der das Hinzufügen eines Elements fehlschlagen kann ein Element nur dann nicht einfügen kann, wenn eine ungeprüfte Ausnahme ausgelöst wird. Die Methode offer Methode ist für den Einsatz konzipiert, wenn das Scheitern eher ein normales als ein Ausnahmeerscheinung ist, z.B. in einer Warteschlange mit fester Kapazität (oder "bounded") Warteschlangen.

Bei der Verwendung einer Warteschlange mit begrenzter Kapazität ist offer() in der Regel add() vorzuziehen, bei dem das Einfügen eines Elements nur durch das Auslösen einer Ausnahme fehlschlagen kann. Und PriorityQueue ist eine unbeschränkte Prioritätswarteschlange auf der Grundlage eines Prioritätshaufens.

Answer 3

Geben Sie einfach entsprechende Comparator zum Konstrukteur :

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

Der einzige Unterschied zwischen offer y add ist die Schnittstelle, zu der sie gehören. offer gehört zu Queue<E> in der Erwägung, dass add ist ursprünglich zu sehen in Collection<E> Schnittstelle. Abgesehen davon tun beide Methoden genau das Gleiche - sie fügen das angegebene Element in die Prioritätswarteschlange ein.

Answer 4

Von Warteschlangen-API :

Die Methode offer fügt ein Element ein, wenn dies möglich ist, andernfalls gibt sie false zurück. Dies unterscheidet sich von der Methode Collection.add, die ein Element nur dann nicht hinzufügen kann, wenn sie eine ungeprüfte Ausnahme auslöst. Die offer-Methode ist für den Einsatz in Fällen gedacht, in denen das Scheitern ein normales und kein außergewöhnliches Ereignis ist, z. B. in Warteschlangen mit fester Kapazität (oder "bounded").

Answer 5

Nicht anders, wie in der Javadoc deklariert:

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