# priority queue sortieren



## Dagobert (17. Mrz 2011)

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 (17. Mrz 2011)

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 (17. Mrz 2011)

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 (18. Mrz 2011)

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 (20. Mrz 2011)

dann markier es doch als erledigt 

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


----------



## Marco13 (20. Mrz 2011)

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

```
...
```
"


----------



## moormaster (20. Mrz 2011)

Dagobert hat gesagt.:


> 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 (20. Mrz 2011)

bei heutigen prozessoren ist es doch egal oder was ?


----------



## Marco13 (20. Mrz 2011)

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


----------



## Dagobert (21. Mrz 2011)

Marco13 hat gesagt.:


> 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 



moormaster hat gesagt.:


> 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 (21. Mrz 2011)

Marco13 hat gesagt.:


> 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.


----------

