Wir alle wissen, dass in Algorithmen, die Gegenstand der Informatik sind, Min Heaps und Max Heaps grundsätzlich Prioritätswarteschlangen sind.
Ich habe verschiedene Methoden für Heaps implementiert, wie build_heap, heapify, Schlüssel erhöhen, etc.
Nun, da ich ein gutes Verständnis davon erlangt habe, wollte ich den funktionalen Aspekt der Java-Sprache nutzen.
Ich googelte und fand PriorityQueue.
Als ich über sie erfuhr, konnte ich keine eingebauten Methoden finden, wie:
Erhöhungsschlüssel (x, k)
Verringerungsschlüssel (y, K)
Ich verwende Heaps für die Implementierung des Dijkstra-Algorithmus, und er verwendet die beiden obigen Operationen, aber jetzt denke ich, ich muss meine eigene Heap-Implementierung durchführen.
Habe ich etwas beim Googeln vermisst?
Antworten:
2 für die Antwort № 1Was können Sie tun? Jedes Element, das Sie in die PriorityQueue einfügen, sollte über ein Attribut verfügen, um seinen Wert zu speichern. Dann sollten Sie einen benutzerdefinierten Vergleicher erstellen, der diesen Wert zur Priorisierung der Elemente der Warteschlange verwendet. Wenn Sie den Wert eines Elements ändern möchten, können Sie das Element aus der PriorityQuery entfernen, seinen Wert ändern und dem Wert erneut hinzufügen. Der benutzerdefinierte Vergleicher wird ausgelöst, um ihn in der Warteschlange zu priorisieren.
Weitere Informationen zur Verwendung der PriorityQuery (z. B. Erstellen eines benutzerdefinierten Komparators und Zuordnen der PriorityQueue finden Sie unter dieser Beitrag)
1 für die Antwort № 2
Während PriorityQueue ist in der Tat ein Haufen, es ist kein "Schulhaufen", der interne Funktionen für Sie sichtbar machen würde. PriorityQueue hat die notwendige Funktionalität, um das zu tun, was es am besten kann (d. h. Elemente nach einer Priorität sortieren). Es ist kein Ausgangspunkt, um eigene Algorithmen zu erstellen.
Sie würden nicht anfangen, einen binären Baum aus einem TreeSet entweder.