Java Priority Queue mit einem benutzerdefinierten anonymen Komparator

Question

Verzeihen Sie mir, wenn dies eine versuchte Frage ist, aber ich habe ein wenig Schwierigkeiten, es herauszufinden.

Ich habe derzeit eine Klasse Knoten, und jeder "Knoten" ist ein Quadrat in einem Labyrinth. Ich versuche, den A * -Algorithmus zu implementieren, so dass jeder dieser Knoten ein f-cost (int) -Datenelement darin hat. Ich habe mich gefragt, ob es eine Möglichkeit gibt, eine Prioritätswarteschlange dieser Knoten zu erstellen und die Variable f-cost als Vergleicher einzurichten?

Ich habe Beispiele online angeschaut, aber alles, was ich finden kann, sind String Priority Queues. Kann ich Comparator für die Node-Klasse implementieren? Wäre es mir möglich, auf das darin gespeicherte Datenelement zuzugreifen?

Vielen Dank!

Answer 1

Absolut.

können Sie ein PriorityQueue auf einem anonymen Comparator an den Konstruktor übergeben Basis verwenden:

int initCapacity = 10; 
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() { 
    public int compare(Node n1, Node n2) { 
     // compare n1 and n2 
    } 
}); 
// use pq as you would use any PriorityQueue 

Wenn Ihr Node Klasse bereits implementiert Comparable Sie nicht einmal einen neuen Comparator definieren müssen, wie die Reihenfolge sein wird wird standardmäßig verwendet. Abgesehen von einer anderen Methode wird die natürliche Reihenfolge zwischen Objekten verwendet.

Answer 2

Von dem Javadocs:

Eine unbegrenzten Prioritätswarteschlange basierend auf einem Prioritäts-Heap. Diese Warteschlange Aufträge Elemente gemäß einer Reihenfolge bei Bauzeiten angegeben, die angegeben wird entweder nach ihrer natürlichen Ordnung (siehe Vergleichbare) oder gemäß einem Komparator

Darüber hinaus unterstützen PriorityQueues generischen Datentypen . Wenn Sie Comparable in Ihrer Node-Klasse implementieren, können Sie daher PriorityQueue<Node> erstellen und normal verwenden.

Alternativ gibt es einen Konstruktor PriorityQueue(int initialCapacity, Comparator<? super E> comparator), der einen Komparator als Teil des PriorityQueue-Konstruktors einnimmt. Wenn Sie diese Methode bevorzugen, muss Ihre Knotenklasse nicht den zusätzlichen Code enthalten, der beim Erben von Comparable benötigt wird.

Answer 3

Es gibt eine PriorityQueue-Klasse in java.util. Sie können das verwenden und entweder die natürliche Reihenfolge (Node implements Comparable) oder einen Vergleicher im Konstruktor verwenden (wenn Sie diesen Code nicht in Ihrer Node-Klasse haben wollen). Jede Klasse kann auf alle Daten innerhalb eines anderen zugreifen, solange Sie es zulassen, indem Sie ein Feld nicht privat machen (potenziell schlechter OOP-Stil) oder eine Accessormethode bereitstellen public int getG(), public int getH(), public int getF() .

Answer 4

public class Node implements Comparable<Node>{ 

    public int compareTo(Node o) { 
     // your comparative function 
     return 0; 
    } 

}

wenn compareTo eine negative int zurückgibt, bedeutet "kleiner als", 0 bedeutet "gleich", 1 bedeutet "größer als"

dass eine Funktion alles, was Sie brauchen, um in der Lage sein, PriorityQueue zu verwenden.

EDIT: Vergleich ist anders, ich vermasselt das.-1 < | 0 = | Ich lese schon aus irgendeinem Grund diese von rechts nach links.