Heap - Versionsgeschichte

Kristin am 18. Januar 2017 um 17:32 Uhr

2017-01-18T17:32:41Z

Kristin am 18. Januar 2017 um 17:30 Uhr

2017-01-18T17:30:51Z

Kristin am 2. Juni 2016 um 12:25 Uhr

2016-06-02T12:25:12Z

Kristin am 1. Juni 2016 um 16:43 Uhr

2016-06-01T16:43:57Z

Hauer: Die Seite wurde neu angelegt: „Ein Heap ist eine besondere Form des Binären Baumes. Je nach auf dem Heap verwendeter Ordnung spricht man von einem Min-, oder von einem M…“

2016-01-26T19:01:09Z

Die Seite wurde neu angelegt: „Ein Heap ist eine besondere Form des Binären Baumes. Je nach auf dem Heap verwendeter Ordnung spricht man von einem Min-, oder von einem M…“

Neue Seite

Ein Heap ist eine besondere Form des [[Binärer Baum | Binären Baumes]]. Je nach auf dem Heap verwendeter Ordnung spricht man von einem Min-, oder von einem Max-Heap. In EINI gehen wir jedoch davon aus, dass ein Heap ein Min-Heap ist. Dabei steht das kleinste Element im Baum immer in der Wurzel. Die beiden Unterbäume einer Wurzel im Heap bilden dabei wiederrum einen Heap gleicher Ordnung.

= Repäsentation =

Ein Heap wird zumeist in Form eines [[Array | Arrays]] gespeichert. Dabei wird meistens, zum Zwecke einfacherer Rechnungen, das Element mit dem Index '''0''' im Array frei gelassen. Ein Kindknoten eines Knotens mit dem Index '''i''' kann dann in den Einträgen'''2i''' und '''2i + 1''' gespeichert und gefunden werden. Entsprechend ist der Elternknoten eines Knotens '''i''' der Eintrag im Array mit dem Index '''i/2'''.

= Ordnung =

Theoretisch kann man mithilfe jeder beliebigen Ordnung einen Heap aufbauen, in dieser Veranstaltung verwenden wir jedoch hauptsächlich '''<''' und '''>'''. Wenn nur von Heap die Rede ist, kann man von einem Min-Heap mit '''<'''-Ordnung ausgehen.

= Eigenschaften =

Die Eigenschaften eines Heaps sind folgendermaßen definiert:

* Ein Heap ist ein links-vollständiger Binärbaum.
* Das Element mit dem kleinsten (größten, ...) Wert steht in der Wurzel
* Jeder Unterbaum ist wiederrum ein Heap

= Operationen =

Auf einem Heap sind folgende Operationen üblich:

* Entfernen der Wurzel
* Einfügen eines neuen Elementes
* Wiederherstellung der Heap-Eigenschaften

== Entfernen der Wurzel ==

Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps durch das letzte Element. Die Wiederherstellung der Heap-Eigenschaft ist dann ein simples Tauschen des nun obersten Elementes mit den kleineren seiner beiden Kinder, bis die Heap-Eigenschaft im ganzen Baum wiederhergestellt ist.

== Einfügen eines neuen Elementes ==

Das Einfügen geschieht durch anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap links-vollständig ist, ist dieses Element dann damit das letzte Element im Heap. Anschließend muss dieses Element im Baum unter Umständen nach ''oben'' wandern, damit die Heap-Eigenschaft wieder gelten kann. Dabei muss jedoch immer nur mit dem Vater verglichen werden. Da der Vater garantiert kleiner ist als sein potentiell anderes Kind, wird bei einem Tausch das nach ''oben'' getauschte Element auch kleiner sein als sein Geschwisterknoten, da er sonst nicht getauscht worden wäre.

== Wiederherstellung der Heap-Eigenschaften ==

Wird ein Element hinzugefügt oder entfernt muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder die neue Wurzel beim Entfernen nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, sind relativ wenige Spezialfälle zu beachten.

@@ Zeile 36: / Zeile 36: @@
 Durch das wiederholte Entfernen der Wurzel erhält man also nach und nach zuerst das kleinste, dann das zweitkleinste, dann das drittkleinste, usw.  Element. Diese Sortierung wird als '''[[Heapsort]]''' bezeichnet.
 == Einfügen eines neuen Elementes ==
-Das Einfügen geschieht durch Anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap linksvollständig ist, ist dieses neue Element damit das letzte Element im Heap.
+Das '''Einfügen''' geschieht durch Anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap linksvollständig ist, ist dieses neue Element damit das letzte Element im Heap.
 Anschließend wird der Heap auf seine Eigenschaften überprüft. Ist das neue Element kleiner als sein Elternteil, wird es mit diesem getauscht. Das neue Element wandert so lange nach ''oben'', bis die Heap-Eigenschaften wiederhergestellt sind. Ein Vergleich mit den Geschwisterknoten ist nicht notwendig. Da das Elternteil immer kleiner als seine Kinder ist, muss ein neues Element, falls es kleiner als sein Elternteil ist, logischerweise auch kleiner als seine Geschwister sein.
 == Wiederherstellung der Heap-Eigenschaften ==
 Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder, beim Entfernen, die neue Wurzel nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, funktioniert das alles problemlos, solange die verwendete Struktur zu Beginn wirklich ein Heap gewesen ist.

@@ Zeile 1: / Zeile 1: @@
 Ein '''Heap''' ist eine besondere Form des [[Binärer Baum | Binären Baumes]]. Je nach auf dem Heap verwendeter Ordnung spricht man von einem Min-, oder von einem Max-Heap.
-In EINI gehen wir jedoch davon aus, dass ein Heap ein '''Min-Heap''' ist. Dabei steht das kleinste Element des Baumes immer in der Wurzel. Die beiden Unterbäume einer Wurzel im Heap bilden dabei wiederum einen Heap gleicher Ordnung.
+= Ordnung =
-= Repräsentation =
+Der Aufbau eines Heaps wird durch seine Ordnung bestimmt. Häufig verwendet werden '''<''' (kleiner) und '''>''' (größer). Der sogenannt Max-Heap hat eine >-Ordnung. Hierbei steht das größte Element des Baumes in der Wurzel. In dieser Veranstaltung wird jedoch, wenn nicht weiter spezifiziert, von einem '''Min-Heap''' ausgegangen. Dieser hat eine <-Ordnung, in der Wurzel steht folglich immer das kleinste Element.
-Ein '''Heap''' wird zumeist in Form eines [[Array | Arrays]] gespeichert. Dabei wird meistens, zum Zwecke einfacherer Rechnungen, das Element mit dem Index '''0''' im Array frei gelassen. Ein Kindknoten eines Knotens mit dem Index '''i''' kann dann in den Einträgen'''2i''' und '''2i + 1''' gespeichert und gefunden werden. Entsprechend ist der Elternknoten eines Knotens '''i''' der Eintrag im Array mit dem Index '''i/2'''.
+Die Ordnung des Heaps gilt auch für seine Unterbäume.
-= Ordnung =
+= Repräsentation =
-Theoretisch kann mithilfe jeder beliebigen Ordnung ein Heap aufgebaut werden. In dieser Veranstaltung verwenden wir jedoch hauptsächlich '''<''' und '''>'''. Wenn nur von '''Heap''' die Rede ist, kann man von einem Min-Heap ausgehen. Dieser hat immer eine '''<'''-Ordnung.
+Ein '''Heap''' wird meistens in Form eines [[Array | Arrays]] gespeichert. Dabei wird, zum einfacheren Rechnen, das Element mit dem Index '''0''' im Array frei gelassen. Das Kind eines Knotens mit dem Index '''i''' kann dann in den Einträgen'''2i''' und '''2i + 1''' gespeichert und gefunden werden. Entsprechend ist der Elternknoten eines Knotens '''i''' der Eintrag im Array mit dem Index '''i/2'''.
 = Eigenschaften =
-Die Eigenschaften eines Heaps sind folgendermaßen definiert:
+Jeder Heap hat folgende '''Eigenschaften''':
-* Ein Heap ist ein links-vollständiger Binärbaum.
+* Ein Heap ist ein [[Baum#Eigenschaften und Begriffe|linksvollständiger Binärbaum]].
-* Das Element mit dem kleinsten (größten, ...) Wert steht in der Wurzel.
+* Das Element mit dem kleinsten Wert steht in der Wurzel.
 * Jeder Unterbaum ist wiederum ein Heap.
 = Operationen =
-Auf einem Heap sind folgende Operationen üblich:
+Auf einem Heap sind folgende '''Operationen''' üblich:
 * Entfernen der Wurzel
@@ Zeile 29: / Zeile 29: @@
 == Entfernen der Wurzel ==
-Je nach Ordnung des Heaps erhält man durch das Entfernen der Wurzel entweder das kleinste oder größte Element.
+Durch das '''Entfernen der Wurzel''' erhält man das kleinste Element.
-Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps (also der Wurzel) durch das letzte Element (also unten rechts in der graphischen Darstellung).
+Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps (also der Wurzel) durch das letzte Element (also in der untersten Ebene ganz rechts).
 == Einfügen eines neuen Elementes ==
-Das Einfügen geschieht durch Anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap links-vollständig ist, ist dieses Element damit das letzte Element im Heap. Anschließend muss dieses Element im Baum unter Umständen nach ''oben'' wandern, damit die Heap-Eigenschaft wieder gelten kann. Dabei muss jedoch immer nur mit dem Vater verglichen werden. Da der Vater garantiert kleiner ist als sein potentiell anderes Kind, wird bei einem Tausch das nach ''oben'' getauschte Element auch kleiner sein als sein Geschwisterknoten, da er sonst nicht getauscht worden wäre.
+Das Einfügen geschieht durch Anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap linksvollständig ist, ist dieses neue Element damit das letzte Element im Heap.
 == Wiederherstellung der Heap-Eigenschaften ==
-Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder die neue Wurzel beim Entfernen nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, sind relativ wenige Spezialfälle zu beachten.
+Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder, beim Entfernen, die neue Wurzel nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, funktioniert das alles problemlos, solange die verwendete Struktur zu Beginn wirklich ein Heap gewesen ist.

← Nächstältere Version		Version vom 2. Juni 2016, 12:25 Uhr
Zeile 41:		Zeile 41:
	== Wiederherstellung der Heap-Eigenschaften ==		== Wiederherstellung der Heap-Eigenschaften ==

−	Wird ein Element hinzugefügt oder entfernt muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder die neue Wurzel beim Entfernen nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, sind relativ wenige Spezialfälle zu beachten.	+	Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach ''oben'' im Baum bewegt werden, oder die neue Wurzel beim Entfernen nach ''unten''. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, sind relativ wenige Spezialfälle zu beachten.