Heap: Unterschied zwischen den Versionen
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| 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. | ||
| − | + | = Ordnung = | |
| − | + | 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. | |
| − | + | Die Ordnung des Heaps gilt auch für seine Unterbäume. | |
| − | = | + | = Repräsentation = |
| − | + | 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 = | = Eigenschaften = | ||
| − | + | Jeder Heap hat folgende '''Eigenschaften''': | |
| − | * Ein Heap ist ein | + | * Ein Heap ist ein [[Baum#Eigenschaften und Begriffe|linksvollständiger Binärbaum]]. |
| − | * Das Element mit dem kleinsten | + | * Das Element mit dem kleinsten Wert steht in der Wurzel. |
* Jeder Unterbaum ist wiederum ein Heap. | * Jeder Unterbaum ist wiederum ein Heap. | ||
= Operationen = | = Operationen = | ||
| − | Auf einem Heap sind folgende Operationen üblich: | + | Auf einem Heap sind folgende '''Operationen''' üblich: |
* Entfernen der Wurzel | * Entfernen der Wurzel | ||
| Zeile 29: | Zeile 29: | ||
== Entfernen der Wurzel == | == Entfernen der Wurzel == | ||
| − | + | 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 | + | 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). |
| − | + | Im Anschluss müssen direkt die Heap-Eigenschaften wiederhergestellt werden. Dies geschieht durch den Tausch der neuen "Wurzel" mit dem kleineren ihrer beiden Kinder. Diese [[Methode]] nennt man '''heapify'''. | |
| + | |||
| + | 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 == | == 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 | + | 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 == | == 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 | + | 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. |
Aktuelle Version vom 18. Januar 2017, 19:32 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.
Inhaltsverzeichnis
Ordnung
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.
Die Ordnung des Heaps gilt auch für seine Unterbäume.
Repräsentation
Ein Heap wird meistens in Form eines 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ägen2i und 2i + 1 gespeichert und gefunden werden. Entsprechend ist der Elternknoten eines Knotens i der Eintrag im Array mit dem Index i/2.
Eigenschaften
Jeder Heap hat folgende Eigenschaften:
- Ein Heap ist ein linksvollständiger Binärbaum.
- Das Element mit dem kleinsten 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
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 in der untersten Ebene ganz rechts).
Im Anschluss müssen direkt die Heap-Eigenschaften wiederhergestellt werden. Dies geschieht durch den Tausch der neuen "Wurzel" mit dem kleineren ihrer beiden Kinder. Diese Methode nennt man heapify.
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.
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.
