Heap as Array: Was, wenn IDs keine Zahlen sind

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Heap as Array: Was, wenn IDs keine Zahlen sind

Beitrag von JRS » 24. Jul 2016 20:36

Hallo,

eine Frage zu Heaps as Arrays, die sich mir stellt, ist, ob man für die IDs denn auch nichtnumerische Werte (z.B. Buchstaben) benutzen kann. Das erscheint mir etwas schwierig, da das Array Positions ja die ID als Index verwendet, um in diesem Arrayeintrag die Position im Heap selbst zu speichern. Wenn man jetzt also (wie im Video zu Dijkstra) als IDs Buchstaben verwenden würde, würde man dann als Index in Positions den jeweiligen ASCII Wert der Buchstaben verwenden?

Analog dazu könnte man sich vielleicht auch ganz andere Objekte zur Benutzung als ID vorstellen. Oder ist das bei dieser speziellen Implementation "Heap as Array" einfach nicht vorgesehen?

Vielen Dank für Klärung!

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Heap as Array: Was, wenn IDs keine Zahlen sind

Beitrag von Prof. Karsten Weihe » 24. Jul 2016 21:34

JRS hat geschrieben: eine Frage zu Heaps as Arrays, die sich mir stellt, ist, ob man für die IDs denn auch nichtnumerische Werte (z.B. Buchstaben) benutzen kann. Das erscheint mir etwas schwierig, da das Array Positions ja die ID als Index verwendet, um in diesem Arrayeintrag die Position im Heap selbst zu speichern. Wenn man jetzt also (wie im Video zu Dijkstra) als IDs Buchstaben verwenden würde, würde man dann als Index in Positions den jeweiligen ASCII Wert der Buchstaben verwenden?
Wenn ich Sie richtig verstehe, dann geht es hier um zwei verschiedene Dinge.

Die Knoten haben aus dem Anwendungskontext heraus irgendeine Beschriftung, zum Beispiel A, B, C ... wie im Dijkstra-Video oder vielleicht statt dessen Darmstadt, Langen, Frankfurt ... Die Beschriftung muss übrigens gar nicht eindeutig sein, also gar keine ID, zum Beispiel 2x Frankfurt in Deutschland.

Die ID, die von Methode Heap as array: insert zurückgeliefert wird, hat damit nichts zu tun. Diese ID ist numerischer Natur, und zu jedem Zeitpunkt ist jede ID höchstens einmal vergeben. Beides würde man auch als zwei verschiedene Attribute in der Knotenklasse halten.

Im Video zu Dijkstra tauchen diese IDs gar nicht auf, sondern jede Zeile von Q ist ein (Key, Value)-Paar: Zu jedem Distanzwert wird zweckmäßigerweise auch ein Verweis auf den Knoten gespeichert, der diesen Distanzwert hat, denn der Algorithmus muss ja auf den Knoten mit minimalem Distanzwert zugreifen. Dieser Verweis auf den Knoten ist im Video durch den Buchstaben symbolisiert.

Klarer geworden?

KW

JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Re: Heap as Array: Was, wenn IDs keine Zahlen sind

Beitrag von JRS » 25. Jul 2016 10:27

Vielen Dank für die schnelle und ausführliche Antwort!

Ich glaube, ich habe es jetzt verstanden. Aber um sicherzugehen formuliere ich es noch mal: Im Array TheHeap würden wir bei Dijkstra dann also jeweils (Key, Value)-Paare speichern, wobei der Key die aktuelle geringste Distanz ist, und der Value ein Objekt vom Typ "Knoten", das (neben beliebigen weiteren Attributen) mindestens eine ganze Zahl ID, die eindeutig ist, sowie in den meisten Fällen zuästzlich bspw. einen Städtenamen wie "Frankfurt", "Darmstadt" etc. besitzt.

Ist das so korrekt?

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Heap as Array: Was, wenn IDs keine Zahlen sind

Beitrag von Prof. Karsten Weihe » 25. Jul 2016 10:38

JRS hat geschrieben: Ich glaube, ich habe es jetzt verstanden. Aber um sicherzugehen formuliere ich es noch mal: Im Array TheHeap würden wir bei Dijkstra dann also jeweils (Key, Value)-Paare speichern
Ja, ich hatte beim Thema Heap as array mündlich dazu gesagt, dass zu jedem Key auch noch ein Value gespeichert wird, der aber auf den Folien nicht auch noch neben den ganzen anderen Informationen, die eh schon ausreichend kompliziert und folienfüllend sind, mit eingezeichnet ist.
JRS hat geschrieben:wobei der Key die aktuelle geringste Distanz ist, und der Value ein Objekt vom Typ "Knoten"
Genauer: ein Verweis auf ein Objekt vom Typ "Knoten" (Referenzsemantik!).
JRS hat geschrieben: das (neben beliebigen weiteren Attributen) mindestens eine ganze Zahl ID, die eindeutig ist ... besitzt.
Ja, diese ID wird von Heap as array: insert zurückgeliefert und hat eine einzige Funktion, nämlich als Parameter für Heap as array: decrease key zu fungieren (womit dann intern im Array theHeap der zugehörige Index mittels einer Indirektion über das Positions-Array identifiziert wird. Das ist übrigens ein gängiges Programmiermuster weit über die Thematik der AuD hinaus.
JRS hat geschrieben: Ist das so korrekt?
Würde ich sagen.

KW

JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Re: Heap as Array: Was, wenn IDs keine Zahlen sind

Beitrag von JRS » 25. Jul 2016 10:47

Vielen Dank, das hat mir sehr geholfen!

Antworten

Zurück zu „AuD: Vorlesung“