Ich habe ein erhebliches Verständnisproblem bei der Unterscheidung von heap-size[A] und size[A].
Nach meinem Verständnis ist size[A] die Länge des Arrays, also dessen Elementanzahl. Aber wie ist dann heap-size[A] zu verstehen? Ist damit die Höhe des Heaps gemeint?
Oder die Anzahl der Elemente eines "Teilheaps"?
Aus den Vorlesungsfolien (VL07):
Ein (biärer) Heap ist eine Datenstruktur, die als ein (fast) vollsändiger biärer Baum angesehen werden kann, wobei der Baum noch die spezielle Heap-Eigenschaft erfüllt.
Der Baum ist auf allen Ebenen vollständig gefüllt außer möglicherweise auf der letzten.
Der Heap wird meist durch ein Array repräsentiert.
länge[A] ist die Anzahl der Elemente des Feldes
heap-größe[A] ist die Anzahl der Elemente im Heap (die in A gespeichert werden).
das Array muss nicht voll befüllt sein, also gibts eine Array-Länge und eine Anzahl Einträge != null
Bei Fragen dieser Art - und auch anderer Art ;-) empfehle ich *dringend* auf
die Literatur (d.h. bei uns den [Cormen]) zurückzugreifen! Die Folien an sich
sind kein Ersatz dafür! Folien sind an die Vorlesung geknüpft und auf denen
kann nicht immer alles drauf stehen, was noch so erzählt wird. Zum Nachbe-
reiten der Vorlesung sind sie bestimmt sehr hilfreich, aber wenn man etwas
nicht versteht, hilft es meist sehr wenig zu versuchen sich das dann z.B. aus
den Beispielen "herauszuextrahieren". Hier ist der Griff zum Buch dann wirklich
empfehlenswert!
Frank :)
Und noch eine Anmerkung: Meist ist das auch schneller! Man scheut ja
gerne und leicht davor zurück, so ein Buch in die Hand zu nehmen, weil
man meint, dass dauert dann wieder eeeeeeeeeeeewig. Tatsächlich ist
es aber oft so, dass man im Buch dann eine Seite liest und gleich das
a-ha-Erlebnis hat.
Frank :)
Wurden Bücher nicht im Bachelor-Studiengang abgeschafft?
Nein! ;-)
Frank - Mitglied der Gemeinschaft der Troll-Fütterer ;-)