Priority Queue - wo ist denn jetzt der Vorteil?

[koerschgen2001]

Hallo zusammen,

ich versuche mir schon den ganzen Tag ne Priority Queue mit einem Heap zusammen zu bauen.
Ich hab schon fertige Scripte gefunden und natürlich auch das interface in den Java Collections. Nur überall stand bisher dass in einer Priority Queue Elemente nach der Priortät geordnet werdne und nicht nach Reihenfolge, aber nirgendwo war ein Beispiel wo das auch zu sehen war. Es waren dann Elemente auf- oder absteigend sortiert.

Da frage ich mich wozu ne Prioritätswarteschlagen, da kann ich auch ne einfache Liste nehmen und darauf nen HeapSort anwenden.

Ich brauch das Ding für den Dijkstra Algorithmus (kürzeste Wege in Graphen) und da wird halt das minimale Element gebraucht. Schafft man auch mit ner einfachen Liste. priority Queue Heap vs. Liste Heap = ?

Ich wäre für ein anschauliches Beispiel dankbar. Ich habe leider noch nichts entsprechendes gefunden, meistens nur theoretische Definitionen.

 

[EOB]

wieso brauchst du für den kürzeste wege algorithmus denn ne prio queue?

grüße

 

[SebiB90]

wieso brauchst du für den kürzeste wege algorithmus denn ne prio queue?

grüße

für den a-star algorithmus brauch man das glaub ich.
da wird dann halt immer erst der wahrscheinlichste, also mit der höchsten priorität genommen.

 

[koerschgen2001]

wieso brauchst du für den kürzeste wege algorithmus denn ne prio queue?

grüße

Das frag ich mich ja auch. Nur in dem Pseudocode den ich habe steht was von ner Prioritätswarteschlange drin die man unter Verwendung eines Heaps implementieren könnte.

 

[EOB]

dann poste mal den pseudocode, bzw. such dir doch mal ne java implementierung aus dem netz und schau dann?

grüße

 

[koerschgen2001]

Es gibt sehr vielfältige Implementierung und ich habe auch schon eine gefunden die für meine Zwecke sehr einfach ist.
Aber ehrlich gesagt hab ich noch nirgendwo einen mit Prioriätswarteschlange gefunden. Es wird zwar oft theoretisch erwähnt, auch in Aufgabenstellungen auf Uni Seiten, aber ne wirkliche Lösung mit Prioritätswarteschlange und Heap hab ich noch nicht gefunden.

Edit: Vielleicht hab ihr ja hilfreiche Tips.

Hier mal der Pseudocode:

algorithm Dijkstra (G, s)
 Eingabe: Graph G mit Startknoten s
for each Knoten u ∈ V[G] – s do
  D[u] := ∞
  od; 
  D[s] := 0; PriorityQueue Q := V;
  while not isEmpty(Q) do
    u := extractMinimal(Q);
    for each v ∈ ZielknotenAusgehenderKanten(u) ∩ Q do
	  if D[u] + γ((u, v)) < D[v] then
	    D[v] := D[u] + γ((u, v));
  	    adjustiere Q an neuen Wert D[v] 
	  fi
  od
od

Stammt übrigens hieraus: Datenstrukturen und Algorithmen

 

[koerschgen2001]

Hier steht übrigens auch dass im Normalfall ne Prioritätswarteschlange verwendet wird.
de.wikipedia.org/wiki/Dijkstra-Algorithmus#Zeitkomplexit.C3.A4t

 

[Prusik]

bei wiki ists ja jetzt beschreiben... die Boxen, die man schon mal angegangen ist, aber die noch nicht ausgewählt wurden, kommen in eine Priority Queue, um dannach der Priorität (Distanz) nach ausgegeben zu werden. Ich habs mit einer ArrayList gemacht und dann manuell gesucht . das ist wohl langsamer als die Priority Queue