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

Übergeben Sie es einem Comparator . Geben Sie den gewünschten Typ anstelle von T

Verwendung von Lambdas (Java 8+):

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

Klassischer Weg, mit anonymer Klasse:

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

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

});

Um in umgekehrter Reihenfolge zu sortieren, vertauschen Sie einfach e1, e2.

Answer 2

Hier können wir einen benutzerdefinierten Vergleicher definieren:

Unter dem Code :

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

Ausgang :

   india                                               
   pakistan                                         
   bangladesh

Unterschied zwischen der Angebots- und der Hinzufügungsmethode : Link

Answer 3

Nur um die Frage zu beantworten add() gegen offer() Frage (da die andere Frage meiner Meinung nach perfekt beantwortet ist, diese aber möglicherweise nicht):

Selon JavaDoc zur Schnittstelle Queue Die Methode offer fügt ein Element ein, wenn dies möglich ist, und gibt andernfalls false zurück. Dies unterscheidet sich von der Methode Collection.add, bei der das Hinzufügen eines Elements nur dann fehlschlagen kann, wenn eine ungeprüfte Ausnahme ausgelöst wird. Die offer-Methode ist für den Einsatz konzipiert, wenn das Scheitern eher ein normales als ein außergewöhnliches Ereignis ist, zum Beispiel in Warteschlangen mit fester Kapazität (oder "bounded")."

Das heißt, wenn Sie das Element hinzufügen können (was bei einer PriorityQueue immer der Fall sein sollte), funktionieren sie genau gleich. Aber wenn Sie das Element nicht hinzufügen können, offer() erhalten Sie eine schöne und hübsche false zurückkehren, während add() löst eine unangenehme ungeprüfte Ausnahme aus, die Sie in Ihrem Code nicht haben wollen. Wenn das Ausbleiben der Hinzufügung bedeutet, dass der Code wie beabsichtigt funktioniert und/oder es sich um etwas handelt, das Sie normalerweise überprüfen werden, verwenden Sie offer() . Wenn das Nichthinzufügen bedeutet, dass etwas kaputt ist, verwenden Sie add() und behandeln die daraus resultierende Ausnahme, die gemäß die Spezifikationen der Sammelschnittstelle .

Sie sind beide auf diese Weise implementiert, um den Vertrag über die Warteschlangenschnittstelle zu erfüllen, der Folgendes festlegt offer() scheitert durch die Rückgabe einer false ( Methode bevorzugt in kapazitätsbeschränkten Warteschlangen ) und auch den Vertrag über die Sammlungsschnittstelle pflegen, der gibt an. add() schlägt immer mit einer Ausnahme fehl .

Wie auch immer, ich hoffe, das klärt zumindest diesen Teil der Frage.

Answer 4

Als Alternative zur Verwendung von Comparator können Sie die Klasse, die Sie verwenden, auch in Ihrem PriorityQueue implementieren Comparable (und überschreiben dementsprechend die compareTo Methode).

Beachten Sie, dass es im Allgemeinen am besten ist, nur Comparable anstelle von Comparator wenn diese Reihenfolge die intuitive Reihenfolge des Objekts ist - wenn Sie zum Beispiel einen Anwendungsfall haben, in dem Sie sortieren müssen Person Objekte nach Alter zu sortieren, ist es wahrscheinlich am besten, einfach die Comparator stattdessen.

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

Sortie :

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

Answer 5

Ich habe mir auch Gedanken über die Druckreihenfolge gemacht. Nehmen wir zum Beispiel diesen Fall:

Für eine Prioritäts-Warteschlange:

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

Dieser Code:

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

kann anders gedruckt werden als:

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

Ich habe die Antwort in einer Diskussion gefunden in einem anderen Forum Ein Benutzer sagte: "Die offer()/add()-Methoden fügen das Element nur in die Warteschlange ein. Wenn Sie eine vorhersehbare Reihenfolge wünschen, sollten Sie peek/poll verwenden, die den Kopf der Warteschlange zurückgeben."