Heap (IntroProg)
Heap (IntroProg)
in einer Nussschale
- Abstrakte Datenstruktur
- Basiert meist auf einem Baum
- Jedes Element hat einen Schlüssel (häufig die Elemente selbst), das die Priorität des Elements festlegt
- Partiell geordneter Baum
Definition
Ein Heap stellt einen Binärbaum in einem Array dar
Aufbau eines Heaps
- Index 1: Enthält das erste Element, welches der Wurzel des Baumes entspricht.
- Index 2: Zeigt auf das zweite Element, das als linkes Kind der Wurzel angesehen wird.
- Index 3: Enthält das dritte Element, welches als rechtes Kind der Wurzel gilt.
- Weitere Indizes: Die anschließenden Elemente werden fortlaufend in der Reihenfolge ihrer Aufzählung (von oben nach unten und von links nach rechts) nummeriert.
- daraus resultieren Regeln um im Baum zu navigieren
Navigation
| Ziel | Berechnung |
|---|---|
| Wurzel | |
| Parent(i) | |
| Left(i) | |
| Right(i) |
Anwendungen
- Sortieren (HeapSort) HeapSort
- Zugriff auf Min/Max in O(1)
- Scheduling
- Etc.
Max-Heap-Bedingung:
-
Die Schlüssel der Kinder eines Knotens sind stets kleiner als die ihres Parent ⇒ an der Wurzel des Baumes ist immer ein Element mit maximalem Schlüssel
!200 -
Min-Heap-Bedingung entsprechend
-
Serialisieren -> zweidiemnsionale Datenstruktur muss eindimensional gemacht werden. Weil das netzwerkkabel eindimensional ist
Binäre Halden: Bäume als Arrays
Array A[1,…,length(A)]- Man kann ein Array als vollständigen Binärbaum interpretieren
- D.h., alle Ebenen des Baums sind voll bis auf die letzte (linksvoll)
- Zwei Attribute: length(A) und heap-size(A), heap-size(A) ≤ length(A)
max Heap property
Für jeden Knoten i außer der Wurzel gilt:
A[Parent(i)] ≥ A[i]
min Heap property
Für jeden Knoten i außer der Wurzel gilt:
A[Parent(i)] ≤ A[i]