Upload
hartwin-nabers
View
106
Download
0
Embed Size (px)
Citation preview
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
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)
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
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
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
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
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...
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)
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.
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)
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?
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“!
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
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!
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!
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!
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)
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
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 =
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 !
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.
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