Die Heap-Datenstruktur¶
Wahl der geeigneten Datenstruktur¶
Beispiele für das Zusammenspiel von Algorithmus mit entsprechenden Datenstrukturen:
- Queue-Datenstruktur für die Implementation der Breitensuche mit linearer Laufzeit
- Stack-Datenstruktur für die iterative Implementation der Tiefensuche mit linearer Laufzeit
Weitere Beispiele für gängige Datenstrukturen¶
- Heaps
- binäre Suchbäume
- Hash-Tabellen
- Bloom-Filter
- Union-Find
„Mache die Dinge so einfach wie möglich – aber nicht einfacher.“
Albert Einstein
Principle of Parsimony¶
Wähle die einfachste Datenstruktur, die alle Operationen unterstützt, die von der Anwendung benötigt werden.
Ein wichtiges Können (skill) für Informatiker:innen ist es tiefe Kenntnisse über Datenstrukturen zu besitzen, damit er/sie diese geeignet einsetzt.
Unterstütze Operationen der Heap-Datenstruktur $H$¶
Insert-Operation für einen Heap $H$ und ein neues Objekt $x$: füge $x$ zu $H$ hinzu.
ExtractMinfür einen Minmal-Heap $H$: gib das Objekt mit dem kleinsten Schlüssel (key) zurück und lösche dieses Objekt aus $H$.
Theorem 10.1¶
In einem Heap mit $n$-Objekten benötigen die Insert und die ExtractMin-Operationen
jeweils $O(\log n)$ Laufzeit.
Hinweis: Ein Standard-Heap kann ExtractMax statt ExtractMin als Operation haben. Aber es ist nicht beides gleichzeitig mit Laufzeit $O(\log n)$ möglich.
Zusätzliche Operationen für $H$¶
FindMin: für einen Heap $H$: finde das Objekt mit dem kleinsten Schlüssel (key).
Kann auch mit ExtractMin und Insert emuliert werden, aber es ist auch eine effizientere direkte Implementation in Laufzeit $O(1)$ möglich.
Heapify: Für eine Liste/Menge von Objekten $x_1, x_2, \dots, x_n$ erzeuge einen Heap $H$ mit den Objekten.
Kann auch durch Iteration über die Objekte in $O(n\log n)$-Laufzeit erreicht werden, aber eine direkte $O(n)$-Implementation ist möglich.
Delete: für einen Heap $H$ und einem Zeiger (pointer) zu einem Objekt $x$ in $H$: Lösche $x$ aus $H$.
Kann in $O(\log n)$-Laufzeit implementiert werden.
Wann sollte man einen Heap verwenden?¶
Wenn die Anwendung eine schnelle Minimum- oder Maximum-Berechnung auf einer sich ändernden Menge von Objekten benötigt.
Pseudocode von HeapSort:¶
Eingabe (Input): Ein Array $A$ mit $n$ Integer-Zahlen in beliebiger Ordnung.
Ausgabe (Output): Ein Array $B$ mit den gleichen Zahlen sortiert aufsteigend beginnend mit dem kleinesten Element.
$H := $ empty Heap
for $i=1$ to $n$ do
Insert$A[i]$ into $H$
for $i=1$ to $n$ do
$B[i]:=$ExtractMinfrom $H$
Quiz¶
Was ist die Laufzeit von HeapSort?
Weitere Anwendungen¶
- Event Manager
- Median Maintenance
Dijkstra-Implementierung mit der Heap-Datenstruktur¶
Proposition 10.4¶
Für jeden gerichteten Graphen $G(V, E)$ und jeden Startknoten $s$ benötigt die Heap-basierte Implementation des Dijkstra-Algorithmus eine Laufzeit von $O\left((m+n)\log n\right)$ mit $m=|E|$ und $n=|V|$.
Idee¶
Schlüssel für den Heap:
$$ key(w) = \min_{(v,w)\in E: v\in X} \left( len(v) + l_{vw}\right) $$mit
- Die Menge $X$ sind die Knoten, für die der kürzeste Weg bereits berechnet wurde.
Dijkstra¶
Input: directed graph $G=(V,E)$ in adjacency-list representation, a vertex $s \in V$, a length $l_e$ for each edge $e \in E$
Postcondition: for every vertex $v \in V$ a length $l(v)$ equals to the true shortest path distance $dist(s,v)$
$X := \{\}$ // empty set
$H := \{\}$ // empty heap
$keys(s)=0$
for every $v\neq s$ do
$keys(v)=\infty$
for every $v \in V$ do // or Heapify
Insert $v$ into $H$
while $H$ is not-empty do // Main loop
$w^*:=$ ExtractMin$(H)$
add $w^*$ to $X$ with $len(w^*):=key(w^*)$
for every edge $(w^*,y)$ with $y \in H$ do // update the heap
Delete$y$ from $H$
$key(y):= \min \left\{ key(y), len(w^*)+l_{w^*y} \right\}$
Insert$y$ into $H$
Warum ist die Laufzeit von Dijkstra $O\left((m+n)\log n\right)$?¶
while $H$ is not-empty do // Main loop ist $O(n)$
...
$w^*:=$ ExtractMin$(H)$ // log(n)
ist in $O(n\log n)$
while $H$ is not-empty do
...
for every edge $(w^*,y)$ do // mit äußerem Loop m-mal
Delete from Heap // log(n)
....
Insert into Heap // log(n)
ist in $O(m \log n)$. Äußerer Loop über alle Knoten, dann loop über alle Kanten vom aktuellen Knoten aus. so werden alle Kanten betrachtet, d.h. $m\log n$
Also insgesamt: $O\left((n+m) \log n\right)$
Implementierung von Heaps¶
Heaps können mit Hilfe von binären Bäumen implementiert werden, die folgende Heap-Eigenschaft haben:
Min-Heaps: Für jedes Objekt $x$ ist der Schlüssel von $x$ kleiner oder gleich dem Schlüssel seiner Kinderknoten.
Max-Heaps: Für jedes Objekt $x$ ist der Schlüssel von $x$ größer oder gleich dem Schlüssel seiner Kinderknoten.
Am einfachsten lässt sich so ein binärer Baum mit Hilfe eines Arrays implementieren. Dabei können die Positionen der Kinder (childs) bzw. des Elternknotens (parent) folgendermaßen berechnet werden (falls die Indizierung mit 1 beginnt!):
| Position des Parent | $\lfloor i/2 \rfloor\text{ wenn } i\geq 2$ |
| Position des linken Kindes | $2i \text{ wenn }2i\leq n$ |
| Position des rechten Kindes | $2i+1 \text{ wenn }2i+1\leq n$ |
Implementierung von Insert in $O(\log(n)$¶
- Hänge das neue Objekt an das Ende des Arrays und erhöhe die Heapgröße um 1.
- Vertausche wiederholt das neue Objekt mit seinen Elternknoten bis die Heap-Eigenschaft des Baumes wieder erfüllt ist.
Beispiel: Einfügen des Wertes 15 in einen Max-Heap¶
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Implementierung von ExtractMin (Min-Heap) bzw. ExtractMax (Max-Heap) in $O(\log(n)$¶
- Extrahiere den Zeiger zum ersten Objekt (root)
- Überschreibe den root-Knoten mit dem letzten Element $x$ und verringere die Heapgröße um 1.
- Vertausche wiederholt $x$ mit dem kleinsten (bzw. größeten) Kind von $x$ solange bis die Heap-Eigenschaft des Baumes wieder erfüllt ist.
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Falls (ein) Kinderknoten größer ist/sind: Tausche mit dem größeren Kinderknoten.
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap