Heap as Array: Invariante von insert und extract minimum

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Heap as Array: Invariante von insert und extract minimum

Beitrag von sbechtel »

Hallo,

auf der Seite der abstrakten Datenstruktur heap as array wird die Heap-Eigenschaft so definiert, dass jedes Kindelement (in der Baumabstraktion) mindestens so groß ist, wie sein Elternelement. Das wird auch dadurch noch mal verdeutlicht, dass die Eigenschaft für Indizes i aus {2, ..., N} gelten soll.

In den Invarianten der Methoden insert und extract minimum wird es aber, wenn ich nicht falsch liege, anders herum dargestellt.

Am leichtesten sieht man dies bei extract minimum. Hier wird k im Induktionsanfang auf 1 gesetzt und die Invariante lautet, dass alle Elemente außer das an Position k die Heap-Eigenschaft erfüllen. Nach der obigen Definition (i aus {2, ..., N}) kann das schon mal gar nicht möglich sein, denn 1 ist offensichtlich nicht in dieser Menge.

In insert ist es umgekehrt, hier wird im Induktionsanfang k = N gesetzt (nachdem N = N+1 gesetzt wurde) und die Invariante besagt, dass das floor(k/2)-te Element die Heap-Eigenschaft erfüllen soll, also in Baumabstraktion wieder der Elternknoten.

Welche Definition der Heap-Eigenschaft ist also richtig? Ich würde sagen, wie sie ursprünglich definiert wir, nämlich mit Kindknoten mindestens so groß wie Elternknoten...

VG Sebastian

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Heap as Array: Invariante von insert und extract minimum

Beitrag von Assax »

In den Videos die zu jedem Thema gemacht worden sind, sind die Kinder so wie ich das gesehen habe Größer als der Vorgänger, auch in der Lösung zur Klausur aus 2013, April sieht es so aus.

Hier das erwähnte Video: https://openlearnware.hrz.tu-darmstadt.de/material/2124 .
Einfach auf "Wie sehen denn Heaps nun aus?" klicken.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Heap as Array: Invariante von insert und extract minimum

Beitrag von sbechtel »

Assax hat geschrieben:In den Videos die zu jedem Thema gemacht worden sind, sind die Kinder so wie ich das gesehen habe Größer als der Vorgänger, auch in der Lösung zur Klausur aus 2013, April sieht es so aus.

Hier das erwähnte Video: https://openlearnware.hrz.tu-darmstadt.de/material/2124 .
Einfach auf "Wie sehen denn Heaps nun aus?" klicken.
Ja, dass hatte ich ja auch so geschrieben:
jedes Kindelement (in der Baumabstraktion) mindestens so groß ist, wie sein Elternelement.
Es geht mir nur darum, ob die Heap-Eigenschaft an einem Knoten geprüft wird, indem man den Knoten mit seinem Elternknoten vergleicht (Definition auf der Heap as Array Seite) oder den Knoten mit seinen beiden Kindern vergleicht (Invariante bei insert und extract minimum).

VG Sebastian

Antworten

Zurück zu „Archiv“