Beispiele für das Zusammenspiel von Algorithmus mit entsprechenden Datenstrukturen:
„Mache die Dinge so einfach wie möglich – aber nicht einfacher.“
Albert Einstein
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.
Insert
-Operation für einen Heap $H$ und ein neues Objekt $x$: füge $x$ zu $H$ hinzu.
ExtractMin
für einen Minmal-Heap $H$: gib das Objekt mit dem kleinsten Schlüssel (key) zurück und lösche dieses Objekt aus $H$.
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.
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.
Wenn die Anwendung eine schnelle Minimum- oder Maximum-Berechnung auf einer sich ändernden Menge von Objekten benötigt.
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]:=$ExtractMin
from $H$
Was ist die Laufzeit von HeapSort
?
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|$.
Schlüssel für den Heap:
$$ key(w) = \min_{(v,w)\in E: v\in X} \left( len(v) + l_{vw}\right) $$mit
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$
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)$
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$ |
Insert
in $O(\log(n)$¶Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
Bildquelle: https://en.wikipedia.org/wiki/Binary_heap
ExtractMin
(Min-Heap) bzw. ExtractMax
(Max-Heap) in $O(\log(n)$¶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