Heap: Unterschied zwischen den Versionen
Hauer (Diskussion | Beiträge) (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…“) |
|||
| 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 | + | 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. | |
| − | 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'''. | + | = Reprä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 = | = Ordnung = | ||
| − | Theoretisch kann | + | 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. |
= Eigenschaften = | = Eigenschaften = | ||
| Zeile 14: | Zeile 16: | ||
* Ein Heap ist ein links-vollständiger Binärbaum. | * Ein Heap ist ein links-vollständiger Binärbaum. | ||
| − | * Das Element mit dem kleinsten (größten, ...) Wert steht in der Wurzel | + | * Das Element mit dem kleinsten (größten, ...) Wert steht in der Wurzel. |
| − | * Jeder Unterbaum ist | + | * Jeder Unterbaum ist wiederum ein Heap. |
= Operationen = | = Operationen = | ||
| Zeile 27: | Zeile 29: | ||
== Entfernen der Wurzel == | == 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 | + | Je nach Ordnung des Heaps erhält man durch das Entfernen der Wurzel entweder das kleinste oder größte 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). | ||
| + | |||
| + | Die Wiederherstellung der Heap-Eigenschaft ist dann ein simples Tauschen des jeweiligen nun obersten Elementes mit dem kleineren seiner beiden Kinder, bis die Heap-Eigenschaft im ganzen Baum wiederhergestellt ist. | ||
== Einfügen eines neuen Elementes == | == Einfügen eines neuen Elementes == | ||
| − | Das Einfügen geschieht durch | + | 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. |
== 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. | ||
Version vom 1. Juni 2016, 18:43 Uhr
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 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.
Inhaltsverzeichnis
Repräsentation
Ein Heap wird zumeist in Form eines 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ägen2i 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 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.
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 wiederum 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
Je nach Ordnung des Heaps erhält man durch das Entfernen der Wurzel entweder das kleinste oder größte 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).
Die Wiederherstellung der Heap-Eigenschaft ist dann ein simples Tauschen des jeweiligen nun obersten Elementes mit dem 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 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.
