+ All Categories
Home > Documents > 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004...

01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004...

Date post: 05-Apr-2015
Category:
Upload: hartwin-nabers
View: 105 times
Download: 0 times
Share this document with a friend
22
01.04.2004 (c) W. Conen, FH GE, GIN2 1 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues - Heap
Transcript
Page 1: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 1

GIN2 – 2. Vorlesung, SS04Prof. Dr. Wolfram Conen

1.4.2004

Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues - Heap

Page 2: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 2

Schnelles Sortieren

6 12 5 9 10 11 1 2 4 8 3 7

1 2 3 4 5 6 7 8 9 10 11 12

Situation: n (Schlüssel-)Werte aus [1,n]Keine Duplikate.

Kosten? O(n)

Page 3: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 3

Schnelles Sortieren: BucketSort

6 12 5 9 6 10 11 1

Töpfe: 6 125 9 10 116

1

1 5 6 6 9 10 11 12Ergebnis:

Situation: m Töpfe, Schlüsselwerte aus [1,m], Duplikate

Page 4: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 4

Schneller Sortieren: BucketSort in mehreren Phasen (Radixsort)

Situation: n Werte aus [0,,nk-1], Duplikate möglichKosten normaler Bucketsort: O(n+nk) Idee: Wir wenden ihn mehrfach an!

Beispiel: n Werte aus [0,,n2-1], m = n1. Phase: Werti einfügen in Bk mit k = Werti MOD m2. Phase: Ergebnisliste durchlaufen,

Werti nach Bk mit k = Werti DIV m, dort am ENDE anfügen

Page 5: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 5

Schneller Sortieren: BucketSort in mehreren Phasen

3 18 24 6 47 7 56 34 98 60

Beispiel: n = 10, Werte aus [0,,99], 1. Phase

3 MOD 10 = 318 MOD 10 = 8

Töpfe:3

1860

24 6985634

47 7

Ergebnis 1. Phase: 60 3 24 34 6 5 47 7 18 98

Page 6: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 6

Schneller Sortieren: BucketSort in mehreren Phasen

60 3 24 34 6 56 47 7 18 98

Beispiel: n = 10, Werte aus [0,,99], 2. Phase

60 DIV 10 = 618 DIV 10 = 1

Töpfe:60

Ergebnis: 3 6 7 18 24 34 47 56 60 98

367 24 34 5618 9847

Page 7: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 7

Bucket/Radix Sort: Review

• Wenn wir die Größe des Schlüsselbereichs als Konstante ansehen, dann sortieren wir zu Kosten von O(n)

• Aus einer sortieren Folge können wir zu Kosten von O(1) das minimale Element finden und entnehmen

• Aber Dijkstra verändert ja auch noch die Distanz-Werte der Knoten...

Page 8: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 8

Priority Queues

• INSERT: Warteschlangen, in die Elemente gemäß einer Priorität eingeordnet werden

• DELETE MIN: Es wird jeweils das Element höchster Priorität entnommen (das soll das Element mit dem minimalen Wert sein)

• Für uns noch wichtig: DECREASE KEY – der Wert eines Knotens verringert sich!

• Das sind genau die Operationen, die wir im Dijkstra brauchen: Initialer Aufbau des Queues (INSERT), Updates der Knotenwerte (DECREASE KEY), Entnahme des „besten“ Knotens (DELETE MIN)

Page 9: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 9

Priority Queues

• Genauer:

– INSERT(Q,v): Füge Knoten v mit Wert Wert(v) in Priority-Queue Q ein

– (Q,v*) Ã DELETE MIN(Q): Liefere den Knoten mit dem minimalen Wert und lösche ihn aus dem Priority-Queue Q, liefere Q zurück

– Q Ã DECREASE KEY(Q,v,Wert): Verringere den (Schlüssel-)Wert des Knotens v auf Wert.

Page 10: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 10

Priority Queues: Implementierung

• Wie kann man das effizient implementieren?

• Z.B. mittels eines sogenannte Heaps! (wir betrachten zunächst nur die Operationen INSERT und DELETE MIN)

• Was ist ein Heap (=Haufen)? Das ist ein partiell-geordneter Baum:

Definition: Ein partiell-geordneter (binärer) Baum ist ein knotenmarkierter binärer Baum T, in dem für jeden Teilbaum T´ mit Wurzel w gilt:

8 y 2 T´: Wert(w) · Wert(y)

Page 11: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 11

Partiell-geordneter Baum

(Schlüssel-)Werte: 4 6 6 7 10 10 12 13 13 19

4

6

12

13 19

6

7

10

13 10

Alle Wurzeln erfüllen die Bedingung! Ist der Baum eindeutig?

Page 12: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 12

Partiell-geordneter Baum(Schlüssel-)Werte: 4 6 6 7 10 10 12 13 13 19

4

6

12

13 19

6

7

10

13

10

Alle Wurzeln erfüllen die Bedingung! Aber der Baum ist nicht mehr „balanciert“!

Page 13: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 13

Heap: INSERT

Algorithm INSERT(Q,v)

Füge v auf der ersten freien Position der untersten Ebene ein (wenn voll, neue Ebene beginnen)

p à Vater(v)

Solange p existiert und Wert(v) < Wert(p) tue

Vertausche die Werte

von p und v; v à p; p à Vater(p)

• Wir betrachten links-vollständige partiell geordnete Bäume:– alle Ebenen bis auf die

letzte sind voll besetzt– auf der letzten Ebene

sitzen die Knoten soweit links wie möglich

Page 14: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 14

Heap: INSERT

Algorithm INSERT(Q,v)

Füge v auf der ersten freien Position der untersten Ebene ein (wenn voll, neue Ebene beginnen)

p à Vater(v)

Solange p existiert und Wert(v) < Wert(p) tue

Vertausche die Werte von p und v; v à p; p à Vater(p)

Einfügen von 5

4

6

12

13 19

6

7

10

13 10

5

p !

à v

Wert(v) < Wert(p)? Klar!Also: Vertauschen!

Page 15: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 15

Heap: INSERT

Algorithm INSERT(Q,v)

Füge v auf der ersten freien Position der untersten Ebene ein (wenn voll, neue Ebene beginnen)

p à Vater(v)

Solange p existiert und Wert(v) < Wert(p) tue

Vertausche die Werte von p und v; v à p; p à Vater(p)

Einfügen von 5

4

6

12

13 19

5

7

10

13 10

6

v !

à p

Wert(v) < Wert(p)? Klar!Also: Vertauschen!

Page 16: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 16

Heap: INSERT

Algorithm INSERT(Q,v)

Füge v auf der ersten freien Position der untersten Ebene ein (wenn voll, neue Ebene beginnen)

p à Vater(v)

Solange p existiert und Wert(v) < Wert(p) tue

Vertausche die Werte von p und v; v à p; p à Vater(p)

Einfügen von 5

4

5

12

13 19

6

7

10

13 10

6

p !

à v

Wert(v) < Wert(p)? Nein!Also: Fertig!

Page 17: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 17

Heap: INSERTIst INSERT korrekt?

Wir betrachten eine einzelne Vertauschung der Werte von v und p, es gilt also Wert(v) < Wert(p).

Wert(p) ist minimal bzgl. aller Unterbäume von p (und damit aller Unterbäume von v – das gilt auch nach dem Positionswechsel!)

Wg. Wert(v) < Wert(p) ist dann auch Wert(v) nach Vertauschung minimal für alle Unterbäume, also ist der neue Baum partiell geordnet (unter der Annahme, dass der Ausgangsbaum partiell geordnet war).

Algorithm INSERT(Q,v)

Füge v auf der ersten freien Position der untersten Ebene ein (wenn voll, neue Ebene beginnen)

p à Vater(v)

Solange p existiert und Wert(v) < Wert(p) tue

Vertausche die Werte von p und v; v à p; p à Vater(p)

Page 18: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 18

Heap: DELETE MINAlgorithm DELETE MIN (Q): (Q, Min)Sei w die Wurzel des Heaps mit den

Söhnen s1, s2;Min à Wert(w)Sei k der letzte Knoten (unten, rechts)Wert(w) à Wert(k); Lösche k; Solange s1 oder s2 existieren und

(Wert(w) > Wert(s1) oder Wert(w) > Wert(s2)) tueVertausche den Wert von w mit dem kleineren Wert der beiden Söhne, dieser Sohn sei s;

w à s; s1 à Linker_Sohn(w); s2 à Rechter_Sohn(w)

Gib Q und Min zurück.

Entfernen des Minimums:

4

5

12

13 19

6

7

10

13 10

6

w !

à k

Page 19: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 19

Heap: DELETE MINAlgorithm DELETE MIN (Q): (Q, Min)Sei w die Wurzel des Heaps mit den

Söhnen s1, s2;Min à Wert(w)Sei k der letzte Knoten (unten, rechts)Wert(w) à Wert(k); Lösche k; Solange s1 oder s2 existieren und

(Wert(w) > Wert(s1) oder Wert(w) > Wert(s2)) tueVertausche den Wert von w mit dem kleineren Wert der beiden Söhne, dieser Sohn sei s;

w à s; s1 à Linker_Sohn(w); s2 à Rechter_Sohn(w)

Gib Q und Min zurück.

Entfernen des Minimums:

6

5

12

13 19

6

7

10

13 10

w !

s1 ! s2 !

Bedingung für s = s1erfüllt! Also: Tauschen

s =

Page 20: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 20

Heap: DELETE MINAlgorithm DELETE MIN (Q): (Q, Min)Sei w die Wurzel des Heaps mit den

Söhnen s1, s2;Min à Wert(w)Sei k der letzte Knoten (unten, rechts)Wert(w) à Wert(k); Lösche k; Solange s1 oder s2 existieren und

(Wert(w) > Wert(s1) oder Wert(w) > Wert(s2)) tueVertausche den Wert von w mit dem kleineren Wert der beiden Söhne, dieser Sohn sei s;

w à s; s1 à Linker_Sohn(w); s2 à Rechter_Sohn(w)

Gib Q und Min zurück.

Entfernen des Minimums:

5

6

12

13 19

6

7

10

13 10

w !

Bedingung nicht erfüllt! Also: Fertig!

s1 ! s2 !

Page 21: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 21

Heap: DELETE MINIst DELETE MIN korrekt?

Wir betrachten eine einzelne vertauschung der Werte von w und s, es gilt also Wert(s) < Wert(w).

Wert(s) ist minimal bzgl. aller Unterbäume von s. Es wurde ausgewählt, also ist es auch minimal im Vergleich zum anderen Kind-Baum – das gilt auch nach dem Positionswechsel!)

w ist möglicherweise nicht minimal für seinen Unterbaum. Das wird aber weiterbehandelt (w sinkt dann weiter!) bis schließlich Wert(w) · Wert(s1) und Wert(w) · Wert(s2).

Algorithm DELETE MIN (Q): (Q, Min)Sei w die Wurzel des Heaps mit den

Söhnen s1, s2;Min à Wert(w)Sei k der letzte Knoten (unten, rechts)Wert(w) à Wert(k); Lösche k; Solange s1 oder s2 existieren und

(Wert(w) > Wert(s1) oder Wert(w) > Wert(s2)) tueVertausche den Wert von w mit dem kleineren Wert der beiden Söhne, dieser Sohn sei s;

w à s; s1 à Linker_Sohn(w); s2 à Rechter_Sohn(w)

Gib Q und Min zurück.

Page 22: 01.04.2004(c) W. Conen, FH GE, GIN21 GIN2 – 2. Vorlesung, SS04 Prof. Dr. Wolfram Conen 1.4.2004 Rund um Dijkstra: - Bucket/Radix-Sort - Priority Queues.

01.04.2004 (c) W. Conen, FH GE, GIN2 22

Priority Queue

• Mit dem Heap lassen sich INSERT und DELETE MIN mit Aufwand O(log n) realisieren!

• Das gleiche gilt für Updates, also DECREASE KEY-Operationen (analog zu INSERT plus schnelles Auffinden, kommt noch)!

• Damit können wir (für sparsam besetzte Graphen) Dijkstra verbessern!

• Wie es noch besser geht: s. Tarjan bzw. die nächste Veranstaltung


Recommended