priority queue sortieren

[Dagobert]

Guten Abend,

Ich habe eine kleine Frage:
Wie kann ich eine priority queue neu sortieren?
Also ich veränder Wertigkeiten in der Queue und möchte diese danach gerne wieder richtig stellen/sortieren. Wie mache ich das am einfachsten? Verwenden tue ich die Hauseigene priority queue von Java.

mfg. Dagobert

 

[Kr0e]

Habe noch nie eine PriorityQueue benutzt, aber aufgrund eines 5 Sekunden Blickes in die Doku:

Comparator<? super E> comparator()
Returns the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering (using Comparable).

Würde mir diesen Comparator zurück geben lassen und dann mit Collections.sort(...) das ganze sortieren. Aber wie gesagt, habe mich nicht näher mit beschäftigt. Nur so als Idee..

 

[Marco13]

Ich nehme an, es geht um effizientes (neu)sortieren, sozusagen mit minimalem Aufwand die richtige Reihenfolge aus Basis der gänderten Prioritäten wieder herzustellen (genaugenommen um eine A*-Suche oder Dijkstra, aber wir wollen die Kristallkugel mal nicht überbelasten 😉 ). Mit der Java-PQ geht das afaik nicht direkt, höchstens durch rausnehmen und neu einfügen oder so... (Ich hatte mal irgendwann angefangen, dafür einen Fibonacci-Heap zu implementieren, aber der ist noch weitgehend ungetestet...)

 

[Dagobert]

Guten Tag,
Marco du hast voll ins schwarze getroffen. Es handel sich um ein Dijkstra der auf nem Scotland Yard Brett Wege sucht. Ich kopiere jetzt einfach alle Elemente in eine neue Queue, damit ist mein Problem behoben. Danke für die schnellen Antworten

mfg. Dagobert

 

[antrox]

dann markier es doch als erledigt 😀

ich lese schon zum 5ten mal etwas, was schon geklaert worden ist und kann nichts dazu beitragen :-((((

 

[Marco13]

Du hättest was beitragen können. Z.B. "Effizient ist aber was anderes - hier ist eine Implementierung vom Fibonacci-Heap:

...

" 😀

 

[moormaster]

Guten Tag,
Marco du hast voll ins schwarze getroffen. Es handel sich um ein Dijkstra der auf nem Scotland Yard Brett Wege sucht. Ich kopiere jetzt einfach alle Elemente in eine neue Queue, damit ist mein Problem behoben. Danke für die schnellen Antworten

mfg. Dagobert

Es ist gar nicht nötig, jedes Mal alle Elemente zu kopieren... die PriorityQueue beim Dijkstra dient doch nur dazu, effizient denjenigen Knoten aus der Warteschlange zu holen, der die geringsten "kosten" vom Startknoten ausgehend hat. Statt zu versuchen, das "alte" Element in der PQ zu aktualisieren kannst Du den betreffenden Knoten einfach nochmal mit den aktualisierten Kosten in die Warteschlange legen. Ist auf jeden Fall effizienter als jedes Mal die ganze PQ zu kopieren.

 

[antrox]

bei heutigen prozessoren ist es doch egal oder was 😀?

 

[Marco13]

Und bei einem Scotland Yard - Spiel sowieso, solange das nicht mehr als 1 Million Felder hat 😀 Aber es geht um's Prinzip 😉

 

[Dagobert]

Und bei einem Scotland Yard - Spiel sowieso, solange das nicht mehr als 1 Million Felder hat 😀 Aber es geht um's Prinzip 😉

Richtig ! Wo komm ich sonst später hin XD (falls ich Später mal nen Scotland Yard World mache 😀 Was nicht nur 200 Felder in Londo hat 😀

Statt zu versuchen, das "alte" Element in der PQ zu aktualisieren kannst Du den betreffenden Knoten einfach nochmal mit den aktualisierten Kosten in die Warteschlange legen

Gute Idee

mfg. Dagobert

 

[Marco13]

Mit der Java-PQ geht das afaik nicht direkt, höchstens durch rausnehmen und neu einfügen oder so...

Dürfte in diesem Fall vermutlich das einfachste sein.