(c) W. Conen, FH GE, ADS, V1.0a 1

ADS – VorlesungProf. Dr. Wolfram Conen

Rund um Dijkstra:

- Heap-Implementierung mit Arrays

- Bottom-Up-Heaps

(c) W. Conen, FH GE, ADS, V1.0a 2

Heap-Implementierung mit Arrays

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

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

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

Dies ist ein Min-Heap, auch ·-Heap.

In Max-Heaps bzw. ¸-Heap gilt Wert(w) ¸ Wert(y), d.h. der Wert jeder Wurzel eines Teilbaums ist größergleich den Werten unter ihr.

Ein Heap kann Priority-Queues unmittelbar implementieren!

Aber wie implementiert man einen Heap?

(c) W. Conen, FH GE, ADS, V1.0a 3

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

Hier unser Heap aus der letzen Vorlesung als Baum...

(c) W. Conen, FH GE, ADS, V1.0a 4

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

Und hier als Array:

Idee: Kinder von Position i sind an Pos. 2i und Pos. 2i+1

4 6 10 12 6 13 10 13 19 7

Pos. 1 2 3 4 5 6 7 8 9 10

(c) W. Conen, FH GE, ADS, V1.0a 5

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) tueVertausche 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

Nun mit Array, nennen wir es H.( Das ist immer eins mehr, als das Ende des

Arrays (also: erweitern!)

Für gerade Pos. v ist p = i/2, sonst (i-1)/2 für i>1 bzw. nichts für Wurzel

( Falls H[i].wert < H[p].wert tuehilfÃH[i].wert; H[i].wertÃH[p].wert; H[p].wertÃhilf;

( Genauso, Vater wie oben finden.

(c) W. Conen, FH GE, ADS, V1.0a 6

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) tueVertausche die Werte von p und v; v à p; p à Vater(p)

Einfügen von 5

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

4 6 10 12 6 13 10 13 19 7 5

p = 5 ( v = 11

vNeu= pAlt= 5pNeu= 2

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

vAlt

4 6 10 12 5 13 10 13 19 7 6

(c) W. Conen, FH GE, ADS, V1.0a 7

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) tueVertausche die Werte von p und v; v à p; p à Vater(p)

Einfügen von 5

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

4 5 10 12 6 13 10 13 19 7 6

pNeu=1

vAlt= 5vNeu= 2

(c) W. Conen, FH GE, ADS, V1.0a 8

Heap: INSERT

Nach dem Einfügen von 5:

4

5

12

13 19

6

7

10

13 10

6

Und als Baum:

4 5 10 12 6 13 10 13 19 7 6

(c) W. Conen, FH GE, ADS, V1.0a 9

Heap: INSERT

Oder „andersherum“:

4

5

12

13 19

6

7

10

13 10

6

4 5 10 12 6 13 10 13 19 7 6

(c) W. Conen, FH GE, ADS, V1.0a 10

Heap: INSERT

Oder „andersherum“ und etwas verzerrt:

4

5

12

13 19

6

7

10

13 10

6

4 5 10 12 6 13 10 13 19 7 6

(c) W. Conen, FH GE, ADS, V1.0a 11

Heap mit Array

DELETE MIN völlig analog

Kleines Randproblem: dynamisch wachsende Arrays in manchen Programmiersprachen kein Problem Oft weiß man auch die Anzahl Objekte vorab und will diese

„nur“ sortieren (oder sortiert ausgeben, wie beim Dijkstra)

Initiales Einfügen aller Elemente per Insert ist dann nicht sehr effizient, soll heißen: es geht besser!

(c) W. Conen, FH GE, ADS, V1.0a 12

Heap mit Array: Aufbau

Annahme: Wir kennen n vorab.

Dann können wir alle Blattpositionen füllen, ohne Vergleiche/Tauschoperationen ausführen zu müssen!

Warum? Das kann die partielle Ordnung nicht verletzen!

Wie geht das?

Wir füllen das Array „von hinten nach vorn“ und beginnen mit dem Einfügen per INSERT erst ab Position (n DIV 2) (für n=10 also Position 5)

(c) W. Conen, FH GE, ADS, V1.0a 13

Heap mit Array: Aufbau (1)

Naives Einfügen-von-vorn (mit INSERT) kostet log1 + log 2 + ... + log n = (n log n)

Jetzt haben wir Kosten für das Füllen von O(n): Sei a ein Array mit n Elementen. Zahl der Vergleiche, um eine partielle Ordnung zu erzeugen, ist

höchstens 2mal so groß, wie die Summe der Entfernungen aller Knoten bis zur Blattebene! (Jeder Knoten sinkt von ganz oben bis ganz unten)

Fortsetzung nächste Folie...

(c) W. Conen, FH GE, ADS, V1.0a 14

Heap mit Array: Aufbau (2)

Die Summe dieser Abstände übersteigt die Zahl n NICHT: Etwas die Hälfte der Knoten sind Blätter, etwa 1/4 hat den Abstand

1, etwa 1/8 den Abstand 2 usw.

Beispiel: n = 31 (Tiefe 4, also 5 Schichten, vollbesetzt) Abstandssumme: 26, allgemein für vollständige Binärbäume der

Tiefe k (mit n = 2k+1 – 1 Knoten): n - k -1 (best case)

Beispiel: n=32 (also Tiefe 5, Schicht 6 hat nur einen Knoten!) Abstandssumme: 31, allgemein mit n = 2k+1

n-1 (worst case) Abstandssumme also insgesamt immer kleiner als n.

(c) W. Conen, FH GE, ADS, V1.0a 15

Heap „verkehrt“

„Normale“ Heapanwendung: Heapsort

Ohne weiteren nennenswerten Platz zu beanspruchen, wollen wir „in situ“ (also direkt „am Ort“) sortieren.

Das geht leichter, wenn wir einen Heap bauen, der eine „umgekehrte“ partielle Ordnungsbedingung erfüllt: die Wurzel ist größergleich als die Söhne (also ein Max- bzw. ¸-Heap)

Dann wenden wir ein DELETE MAX an und tauschen die Wurzel (n-1)-mal gegen das letzte Element des Heaps (und verkürzen diesen dann „von hinten“ und sammeln so dahinter die geordneten Elemente ein! (s. Applet))

(c) W. Conen, FH GE, ADS, V1.0a 16

Heapsort improved

„Normaler“ Heapsort (wie gerade beschrieben) hat Worst- und average-case-Kosten von 2n log n + O(n)

Zur Erinnerung: Quicksort im average-case: 1,386 n log n + O(n), worst-case: O(n2)

Aber Heap-Sort kann es noch besser!

(c) W. Conen, FH GE, ADS, V1.0a 17

Bottom-Up Heapsort

Bisher haben wir beim Einsinken gleich Ordnung geschaffen: Der kleinere Sohn wurde ausgewählt und zur neuen Wurzel

gemacht. Das sind 2 Vergleiche: Söhne miteinander, Wurzel gegen

kleineren (bei Min-Heap) bzw. größeren Sohn (bei Max-Heap).

Jetzt stellen wir uns vor, wir hätten beispielsweise einen Min-Heap bis zum Element a[2] bereits gefüllt und organisiert und fügen nun die Wurzel a[1] hinzu.

Jetzt suchen wir zunächst eine „virtuellen“ Einsinkepfad bis ganz nach unten... indem wir nur zwischen den Söhnen vergleichen und in

Richtung des kleineren Sohn weitergehen...

(c) W. Conen, FH GE, ADS, V1.0a 18

Bottom-Up Heapsort

... und folgen dann dem eben beschrittenen Pfad solange wieder nach oben, bis wir den Wert von a[1] an die Stelle des momentan betrachteten

Elements q schreiben können dort ist erstmals a[1] > q.

Dann lassen wir den Wert des momentan betrachteten Elements und alle anderen Werte auf die Position ihrer Väter rutschen

(die Wurzel ist ja gerade leer, die wird zuletzt gefüllt, dann stoppen wir natürlich)

Auf den nächsten Folien findet sich ein Beispiel!

[Bottom-Up-Heapsort ist eine Idee von Prof. Wegener, U DO]

(c) W. Conen, FH GE, ADS, V1.0a 19

Min?

Min?

Min?

Min?

Bottom-Up Heapsort: Down-Phase

4

6

12

13 19

11

17

15

17 20

12

10

12 11

13 16 17 11

13

·-Heap, Wurzel mit Wert 12 wird einsortiert.

: „Virtueller“ Einfügepfad

4

6

11

13

(c) W. Conen, FH GE, ADS, V1.0a 20

12 > ?

<12?

Bottom-Up Heapsort: Up-Phase (1)

4

6

12

13 19

11

17

15

17 20

12

10

12 11

13 16 17 11

13

·-Heap, Wurzel mit Wert 12 wird einsortiert.

4

6

11

13

: Suche nach Einfügepunkt

11

(c) W. Conen, FH GE, ADS, V1.0a 21

Bottom-Up Heapsort: Up-Phase (2)

4

6

12

13 19

11

17

15

17 20

12

10

12 11

13 16 17 11

13

·-Heap, Wurzel mit Wert 12 wird einsortiert.

4

6

11

13

: Ringtausch

11

12

4

6

11

12

(c) W. Conen, FH GE, ADS, V1.0a 22

Bottom-Up Heapsort: Performance

Geht der Ringtausch bis zur Tiefe t (t · log n), erfordert das log n + (log n – t) = 2 log n – t Vergleiche.

Gerade haben wir 4 + 2 Vergleiche benötigt (die grünen Ovale)! „Normaler Heapsort“ hätte 8 Vergleiche benötigt (warum?)

Das benötigt im average case („Durchschnittsfall“) sehr nahe an 1*n*log n + O(n) – und besser geht es auch theoretisch für Sortierverfahren mit paarweisen Schlüsselvergleichen kaum!

(c) W. Conen, FH GE, ADS, V1.0a 23

Bottom-Up Heapsort: Performance

In Experimenten war Bottom-Up-Heapsort etwa ab n > 400 besser, als Quicksort ...

... und ab n > 16000 besser, als Clever-Quicksort

bei Quicksort sind die Konstanten im Faktor O(n) also günstiger, so dass er für kleine n, trotz der schlechteren Konstante vorne, besser ist.

Für größere n ist aber Bottom-Up-Heapsort besser (mit sich vergrößerndem Vorsprung)!

(genaue Analyse in Güting/Dieker)

(c) W. Conen, FH GE, ADS, V1.0a 24

Literatur

Allgemein zur Algorithmik: Cormen, Leierson, Rivest: Introduction to Algorithms, MIT Press, 2001, 1184

Seiten, knapp über 60 Euro (DAS Standardwerk, sehr präzise, schön gesetzte Darstellung, Englisch, leider teuer, aber etwas, das man immer wieder in die Hand nehmen kann – allerdings ohne Bottom-Up-Heapsort!) – gibt es seit Oktober 2004 auch übersetzt für knapp 70 € vom Oldenbourg-Verlag (zur Qualität der Übersetzung kann ich nich nichts sagen)

Bernd Owsnicki-Klewe: Algorithmen und Datenstrukturen, 2002, Wißner-Verlag, sehr gut lesbarer, hinreichend präziser „Standard“-Streifzug durch die Algorithmik, recht knappe Darstellung, aber nette Auswahl, orientiert sich u.a. auch an Cormen et. al (hat deshalb auch nichts zu Bottom-Up-Heaps), 15,80 €

Ergänzend Güting, Dieker: Datenstrukturen und Algorithmen, Teubner, 2. Aufl., 2003

(krumme Grafiken und nicht sehr übersichtlich gesetzt, sonst sehr nett, Reihenfolge nicht immer glücklich gewählt – vom Problem zur Datenstruktur ist meist besser als umgekehrt, aber insgesamt les- und brauchbar, gibt es jetzt in der 3. Auflage für 29,90 – mit Bottom-Up-Heaps)

Uwe Schöning: Algorithmik, Spektrum, 2001 (runder, tiefer, aber auch knapp und nicht leicht)

Ottmann, Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2002, dick und teuer (noch teuer derzeit, als Cormen, Leierson, Rivest, und nicht ganz so schön, aber umfassend und erprobt.

(c) W. Conen, FH GE, ADS, V1.0a 25

Literatur

Speziell zu Heaps (für angehende Heap-Fans) z.B. Stefan Edelkamps (Juniorprof. an der Uni DO) Diplomarbeit:

Weak-Heapsort: Ein schnelles Sortierverfahren

... und jede Menge Forschungspapiere, z.B. On the Performance of Weak-Heapsort (Edelkamp, Wegener, 1999) etc.

(das brauchen sie natürlich nicht zu lesen, aber hier finden Sie Startpunkte, wenn sie ein „Sortier“-Spezialist werden wollen ;-)