5.5 Prioritätswarteschlangen...97 Löschen aus einem MinHeap Um die Heap-Eigenschaften wiederherzustellen, laufen wir von der Wurzel in Richtung der Blattknoten hat der aktuelle Knoteneinen

72

5.5 Prioritätswarteschlangen§ LIFO- und FIFO-Warteschlangen entfernen Werte aus

der Warteschlange in Abhängigkeit davon,wann sie in diese eingefügt wurden

§ Prioritätswartschlangen interpretieren die Werte als Prioritäten und entfernen immer den kleinstenbzw. den größten Wert

§ MinHeaps („Haufen“) sind Prioritätswarteschlangenbei denen immer der kleinste Wert entfernt wird

Informatik 1 / Kapitel 5: Datenstrukturen

73

Binäre Bäume§ Definition: Ein binärer Baum besteht aus Knoten

§ jeder Knoten hat bis zu zwei Kindknoten,einen linken und einen rechten

§ auf jeden Knoten wird von höchstenseinem Elternknoten verwiesen

§ Knoten, die keine Kindknoten besitzen,heißen Blattknoten (kurz: Blätter)

§ es gibt höchstens einen Knoten ohne Elternknoten,dieser wird als Wurzel bezeichnet


74

Binäre Bäume§ Beispiel:

§ Der Knoten 8 ist die Wurzel des Baums

§ Die Knoten 6, 2 und 1 sind Blattknoten

§ Der Knoten 5 ist Elternknoten seiner Kindknoten 6 und 2


8

5 1

6 2

75

Tiefe und Höhe§ Die Tiefe eines Blattknotens entspricht der Zahl der

Verweise, denen man von der Wurzel aus folgenmuss, um zu ihm zu gelangen

§ Die Höhe eines binären Baums ist die maximale Tiefeseiner Blattknoten erhöht um 1


76

Tiefe und Höhe§ Beispiel:

§ Die Blattknoten 6 und 9 haben Tiefe 2

§ Der Blattknoten 3 hat Tiefe 1

§ Die Höhe des Baumes beträgt damit 3


2

1 3

6 9

77

Vollständiger binärer Baum§ Definition: Ein binärer Baum heißt vollständig, wenn

§ sich die Tiefe seiner Blattknoten ummaximal 1 unterscheidet

§ alle Ebenen außer der Blattebene gefüllt sind

§ die Blattebene von links nach rechts gefüllt ist


78

Vollständiger binärer Baum§ Beispiel:


2

5 1

6 4

2

1 7

4

79

Vollständiger binärer Baum§ Beispiel:


2

5

4 9

2

1 7

6 2

5

80

Vollständige binäre Bäume als Arrays

§ Wir können vollständige binäre Bäume mit Hilfe von Arrays implementieren, indem wir den Baum Ebene für Ebene von links nach rechts durchlaufen und die Wertein dieser Reihenfolge im Array speichern


2

3 7

6 2

2 3 7 6a 2

n = 5

0 1 2 3 4 5 6

81

Vollständige binäre Bäume als Arrays§ Wir verwenden ein statisches Array und merken uns

wiederum in einem Wert n, wie viele Werte bereitsdarin gespeichert sind

§ Das statische Array kann durch ein dynamisches Arrayersetzt werden, so dass der binäre Baum beliebigwachsen und schrumpfen kann


82

Vollständige binäre Bäume als Arrays§ Speichern wir einen vollständigen binären Baum als

Array, so gelten die folgenden Eigenschaften

§ die Wurzel des Baumes befindet sich in a[0]§ der linke Kindknoten des Knotens in a[i]

befindet sich in a[2*i + 1]§ der rechte Kindknoten des Knotens in a[i]

befindet sich in a[2*i + 2]§ der Elternknoten des Knotens in a[i]

befindet sich in a[(i-1)/2]


83

Vollständige binäre Bäume als Arrays§ Beispiel:

§ Die Wurzel befindet sich in a[0]

§ Die Kindknoten des Knotens in a[1]befinden sich in a[3] und a[4]


2

1 7

6 9

2 1 7 6a 9

n = 5

0 1 2 3 4 5 6

84

MinHeap§ Definition: Ein MinHeap ist ein vollständiger binärer

Baum, bei dem der Wert jedes Knotens kleiner gleichals die Werte seiner Kindknoten ist

§ Beispiel:


3

5 4

9 5

85

MinHeap§ Beispiel:


3

5 2

8 5

1

2 7

6 2

7

86

MinHeap§ Wir implementieren MinHeaps mit Hilfe eines Arrays


3

4 7

6 9

3 4 7 6a 9

n = 5

0 1 2 3 4 5 6

87

MinHeap


1 public class MinHeap {

2

3 // Array zum Speichern der Werte

4 private int a[];

5

6 // Anzahl bisher gespeicherter Werte

7 private int n;

8

9 /**

10 * Lege einen MinHeao der angegebenen Gr oße an

11 */

12 public MinHeap (int size) {

13 a = new int[size ];

14 n = 0;

15 }

16

17 // Definition der Methoden folgt ...

18

19 }

88

Einfügen in einen MinHeap§ Um einen Wert in einen MinHeap einzufügen, für diesen

an der Stelle a[n] in das zugrundeliegende Array ein

§ Hierdurch können die Heap-Eigenschaften verletztwerden, so dass wir diese wiederherstellen müssen


89

Einfügen in einen MinHeap§ Beispiel:


2

5 3

8 5

2 5 3 8a 5

n = 5

0 1 2 3 4 5 6

2

5 3

8 5

2 5 3 8a 5 1

n = 6

0 1 2 3 4 5 6

enqueue(1)

1

90

Einfügen in einen MinHeap§ Um die Heap-Eigenschaften wiederherzustellen, laufen

wir vom eingefügten Knoten in Richtung der Wurzel

§ hat der aktuelle Knoten einen Wert, der kleiner alsder Wert seines Elternknotens ist, so vertauschenwir die beiden Werte

§ hat der aktuelle Knoten einen Wert, der größer gleichals der Wert seines Elternknotens ist, oder haben wirdie Wurzel erreicht, so sind die Heap-Eigenschaftenwiederhergestellt


91



2

5 3

8 5

2 5 3 8a 5 1

n = 6

0 1 2 3 4 5 6

2

5 1

8 5

2 5 1 8a 5 3

n = 6

0 1 2 3 4 5 6

31

92



1

5 2

8 5

1 5 2 8a 5 3

n = 6

0 1 2 3 4 5 6

3

Heap-Eigenschaftenwiederhergestellt

93

Einfügen in einen MinHeap


1 public void enqueue (int k) {

2 // Wert in Array einf ugen

3 a[n] = k;

4 n++;

5

6 // Heap - Eigenschaft wiederherstellen

7 int i = n - 1;

8 while (i > 0) {

9 // Elternknoten bestimmen

10 int p = (i - 1) / 2;

11

12 // Heap - Eigenschaft verletzt ?

13 if (a[i] < a[p]) {

14 swap(i, p);

15 i = p;

16 } else {

17 break ;

18 }

19 }

20 }

94

Einfügen in einen MinHeap§ Im schlechtesten Fall laufen wir also vom eingefügten

Knoten bis zur Wurzel und vertauschen die Werteauf diesem Weg

§ Die Laufzeit hierbei hängt damit von der maximalenHöhe eines MinHeaps mit n Werten ab

§ Wir werden uns später überlegen, wie hoch ein MinHeapmit n Werten maximal sein kann


95

Löschen aus einem MinHeap§ Um den minimalen Wert aus einem MinHeap zu entfernen,

ersetzen wir den Wert an der Stelle a[0] durch den Wertan der Stelle a[n-1] und verkleinern den Wert von n

§ Hierdurch können die Heap-Eigenschaften verletztwerden, so dass wir diese wiederherstellen müssen


96

Löschen aus einem MinHeap§ Beispiel:


2 5 3 8a 5 6 4

n = 7

0 1 2 3 4 5 6

4 5 3 8a 5 6

n = 6

0 1 2 3 4 5 6

dequeue() 4

5 3

8 5 6

2

5 3

8 5 6 4

97

Löschen aus einem MinHeap§ Um die Heap-Eigenschaften wiederherzustellen, laufen

wir von der Wurzel in Richtung der Blattknoten

§ hat der aktuelle Knoten einen Wert, der größer als dieWerte seiner beiden Kindknoten ist, so vertauschenwir ihn mit dem kleineren der beiden Werte

§ hat der aktuelle Knoten einen Wert, der größer als derWert eines seiner Kindknoten ist, so vertauschenwir die beiden Werte

§ hat der aktuelle Knoten einen Wert, der kleiner gleich alsdie Werte seiner beiden Kindknoten ist, so sind dieHeap-Eigenschaften wiederhergestellt


98



3 5 4 8a 5 6

n = 6

0 1 2 3 4 5 6

3

5 4

8 5 6

4 5 3 8a 5 6

n = 6

0 1 2 3 4 5 6

4

5 3

8 5 6

99



3 5 4 8a 5 6

n = 6

0 1 2 3 4 5 6

3

5 4

8 5 6

Heap-Eigenschaftenwiederhergestellt

100

Löschen aus einem MinHeap


1 public int dequeue () {

2 int result = a[0];

3

4 // Ersten Wert aus Array entfernen

5 swap (0, n - 1);

6 n--;

7

8 // Heap - Eigenschaft wiederherstellen

9 int i = 0;

10 while (i < n / 2 - 2) {

11

12 // Linker Kindknoten

13 int l = 2 * i + 1;

14

15 // Rechter Kindknoten

16 int r = 2 * i + 2;

17

18 // Kleinerer Kindknoten

19 int c = l;

20 if (a[r] < a[l]) {

21 c = r;

22 }

23

24 // Heap - Eigenschaft verletzt ?

25 if (a[c] < a[i]) {

26 swap(c, i);

27 i = c;

28 } else {

29 break ;

30 }

31 }

101

Löschen aus einem MinHeap§ Im schlechtesten Fall laufen wir also von der Wurzel

bis zum Elternknoten eines Blattknotens undvertauschen die Werte auf diesem Weg

§ Die Laufzeit hierbei hängt damit von der maximalenHöhe eines MinHeaps mit n Werten ab

§ Wir werden uns später überlegen, wie hoch ein MinHeapmit n Werten maximal sein kann


102

Maximale Höhe eines MinHeaps mit n Knoten§ Wie hoch kann ein vollständiger binärer Baum, und

damit ein MinHeap, mit n Knoten maximal sein?

§ Wie viele Knoten enthält ein vollständiger binärer Baumder Höhe h minimal und maximal?

§ die erste Ebene beinhaltet 1 Knoten

§ die zweite Ebene beinhaltet 2 Knoten

§ …

§ die h-te und letzte Ebene beinhaltet minimal 1 Knotenund maximal 2h-1 Knoten


103

Maximale Höhe eines MinHeaps mit n Knoten§ Damit enthält ein vollständiger binärer Baum der Höhe h

minimal 2h-1 Knoten und maximal 2h - 1 Knoten

§ Ein vollständiger binärer Baum mit n Knoten muss somit eine Höhe von höchstens h = ⎡log2(n) + 1⎤ haben

§ Damit wissen wir das Einfügen und Löschen in bzw. auseinem MinHeap Laufzeit in O(log n) hat


104

HeapSort§ HeapSort ist ein weiteres Sortierverfahren, welches die

Werte in einen MinHeap einfügt und diese dannnacheinander in aufsteigender Reihenfolgewiederum aus dem MinHeap entnimmt

§ Das Einfügen und Löschen jedes der n Werte hat Laufzeitin O(log n) und HeapSort hat damit insgesamtLaufzeit in O(n log n)


105

Zusammenfassung§ Binäre Bäume bestehen aus Knoten, wobei jeder

maximal zwei Kindknoten besitzt, und könnenmit Hilfe statischer Arrays implementiert werden

§ MinHeaps als Warteschlangen, welche immer den kleinsten Wert entfernen, sind vollständige binäreBäume und unterstützen das Einfügen undLöschen in Laufzeit O(log n)

§ HeapSort als weiteres Sortierverfahrenmit Laufzeit in O(n log n)


106

Literatur[1] H.-P. Gumm und M. Sommer: Einführung in die

Informatik, Oldenbourg Verlag, 2012 (Kapitel 4)

[2] T. H. Cormen, C. E. Leiserson, R. Rivest undC. Stein: Algorithmen – Eine Einführung,Oldenbourg Verlag, 2009 (Kapitel 6)


Documents

5.5 Prioritätswarteschlangen...97 Löschen aus einem MinHeap Um die Heap-Eigenschaften wiederherzustellen, laufen wir von der Wurzel in Richtung der Blattknoten hat der aktuelle Knoteneinen