Guten Tag, wir haben uns beim letzten Mal mit Prioritätslisten
beschäftigt und haben ein erstes Beispiel, würde ich sagen, für eine
nicht triviale Datenstruktur gesehen, neben den Hashtabellen.
Ich hoffe, ich habe deutlich gemacht, dass man die recht häufig
braucht.
Wir haben dann zwei Varianten kennengelernt, adressierbar und nicht
adressierbar.
Und wir haben eine einfache und recht effiziente Implementierung
kennengelernt, nämlich binäre Heaps.
Vielleicht nochmal eine Wiederholung, wie die funktionieren.
Das ist vielleicht das Wichtigste, was Sie hier mitnehmen sollten.
Heapeigenschaft bedeutet, dass jeder Knoten, also Heaps sind Bäume und
die Knoten haben Schlüssel, die größer gleich sind ihrem
Vorgängerknoten.
Daraus folgt nicht nur, dass die Wurzel das Minimum enthält, was man
für Prioritätslisten haben will, sondern dass Änderungen, also
Einfügen und Löschoperationen, sich darauf beschenken können, entlang
eines Fades zwischen Wurzel und einem Blatt bestimmte
Austauschoperationen durchzuführen.
Damit kriegen wir logarithmische Ausführungszeit für Einfügen und
Minimum entfernen.
Ein weiteres wichtiges Feature, das man auch in anderen Anwendungen
brauchen kann, ist, binäre Heaps sind zwar mathematisch gesehen Bäume,
aber in der Implementierung genügt es, ein einfaches Array zu haben,
weil das ein vollständiger Binärbaum ist, den wir sehr einfach in
dieses Array einbinden können.
Und dann ist linker Nachfolger einfach zweimal aktuelle Position und
rechter Nachfolger zweimal aktuelle Position plus eins und Vorgänger
ist aktuelle Position halbe.
Dann haben wir da konkrete Funktionen für Einfügen und Löschen
gefunden.
Heap aufbauen ging sogar noch ein bisschen schneller als durch
einmaliges Einfügen, nämlich in linearer Zeit, indem man sozusagen
rückwärts durch den Heap durchgeht und die Heap-Eigenschaft sukzessive
herstellt.
Man kann dann mithilfe von Heaps auch sortieren in O von N log N.
Das ist ein echter In-Place-Algorithmus, der also nur konstanten
zusätzlichen Platz braucht.
Vergleich zeigt jetzt, dass Heapsort eigentlich in allen wichtigen
Aspekten asymptotisch sehr gut ist, allerdings in der Praxis halt
langsamer als Quicksort und Mergesort, vor allem weil das Ganze nicht
so cash-effizient ist.
Und man braucht auch ein paar mehr Vergleiche, zweimal so viele wie
Mergesort etwa.
Genau, adressierbare Prioritätslisten haben zusätzlich die Operation
Entfernen und Schlüsselverkleinern und auch noch eine Merge-Operation,
also zwei Mengen zusammenfügen.
Es gibt für alle diese Varianten schnelle Algorithmen.
Zum Beispiel ein Binärer Heap, da braucht man im Wesentlichen nur
hergehen und die direkte Eintragung der Elemente in die Arrayzellen
ersetzen durch Items, deren Position im Speicher sich nicht ändert und
verweise hin und her zwischen dem Array und diesen Elementen.
So, damit waren wir auch schon fertig mit den Prioritätslisten und ich
komme dann zu einem neuen Kapitel, Sortierte Folgen.
Das Bild, das Sie hier sehen, ist ein Ausschnitt von einer inzwischen
ausgestorbenen Technologie, nämlich Karteikästen, die aber trotzdem
sehr instruktiv sind.
Wer hat noch dieses Jahr ein Telefonbuch benutzt und darin
nachgeschlagen von Ihnen?
Das sind Einzelne.
Wer hat ein Karteikasten benutzt?
Das sind auch immer noch Einzelne.
Also algorithmisch finde ich Karteikästen spannend.
Also ein Telefonbuch ist halt dieses sortierte Array.
Ich kann das eigentlich nur schwierig ändern.
Wenn ich irgendwo was einfügen will, muss ich alles neu drucken.
Ein Karteikasten, da kann ich einzelne Karteikarten einfügen oder auch
welche rausnehmen und die Funktionalität bleibt die gleiche.
Also früher war das halt so, dass man in großen Bibliotheken nur über
diese Karteikästen eine Chance hatte, überhaupt was zu finden.
Und wir werden dann so am Rande sogar sehen, dass diese Karteikasten
-Idee auch eine recht direkte Übersetzung in Datenstrukturen hat.
Und daher finde ich das auch spannend.
Jetzt werden wir aber trotzdem wieder etwas mathematischer.
Wir wollen abstrakt gesehen, also mathematisch gesehen, eine sortierte
Folge repräsentieren.
Element 1 bis Element n mit der Eigenschaft, dass e1 kleiner gleich e2
und so weiter kleiner gleich en ist.
Es gibt eine ganze Menge Operationen, die man darauf durchführen will,
aber die vielleicht wichtigste, ich nenne das mal eine kennzeichnende
Operation, weil es eine ist, die die meisten Konkurrenzdatenstrukturen
nicht effizient unterstützt.
Nenne ich Locate.
Da suche ich im Endeffekt das kleinste Element in der Liste, das
größer gleich einem gegebenen Schlüssel ist.
Und mit Address of meine ich jetzt, dass ich nicht wirklich dieses
Element zurückgeben will, sondern die Position innerhalb der
Datenstruktur, damit ich dann in der Datenstruktur auch was tun kann.
Also ich würde zum Beispiel einen Zeiger oder einen Händel oder was
immer zurückgeben von diesem Element innerhalb der Datenstruktur.
Eine Möglichkeit, das zu implementieren, und so werden wir das hier
auch machen, ist, die eigentlichen Elemente in einer
doppeltverketteten Liste zu speichern, sogar mit unserem beliebten
Dummy -Element.
Und dann haben wir die zusätzliche Vereinbarung, dass wir dem einen
Schlüssel unendlich geben, also etwas, das größer ist als jedes echte
Element.
Und dann würde dieses Locate, dem würde man einen Schlüssel geben, der
sucht dann mithilfe einer Navigationsdatenstruktur möglichst schnell
das spezifizierte Element.
Also zum Beispiel, wenn ich Schlüssel 12 hätte, würde ich die 13
suchen.
Wenn ich Schlüssel 13 hätte, würde ich auch die 13 suchen.
Wenn ich Schlüssel 15 hätte, möchte ich die 17 haben und so weiter.
Das könnte ich auch direkt über die doppeltverkettete Liste, aber dann
müsste ich irgendwie von Anfang an durchsuchen.
Das wäre Laufzeit Omega n.
Wir werden sehen, dass wir das in O von Log n schritten können.
Das ist auch die Zeit, die man in einem Array sucht, mit binärer
Suche.
Gibt es dazu Fragen?
So zum Warmwerden möchte ich mal die binäre Suche vorstellen.
Ich denke, die kennen Sie aus Grundbegriffe der Informatik, aber ich
sehe das trotzdem als eine gute Möglichkeit, diese Problematik, was
ist eine sortierte Folge mit einer beschränkten Funktionalität schon
mal vorzustellen und auch noch mal intensiv diese Schleifeninvarianten
zu üben.
Also wir haben ein Array A mit Elementen A1 bis A n.
Und ein Element oder in dem Fall ein Schlüssel reicht auch K.
Und wir haben halt diese Locate-Operation.
Also wir suchen die Position in dem Array, die kleinste Position in
dem Array mit einem Element, das den Schlüssel größer gleich K hat.
Und wir machen jetzt wieder so eine Annahme, dass wir hier Wächter
-Elemente haben, A0 und A n plus 1, die keine echten Elemente
speichern, sondern irgendwie so Dummies mit Schlüsseln minus unendlich
und plus unendlich.
Eine Übungsaufgabe ist dann, sich zu überlegen, ob man die wirklich
braucht.
Meine Hoffnung ist, ich weiß es gar nicht mehr so genau, überlegen Sie
sich wirklich mal, dass so wie der Code geschrieben ist, die Dinger
nie zugegriffen werden.
Und deshalb muss ich sie auch nicht explizit abspeichern.
Aber sozusagen die Invariante nimmt das an, dass es die Dinger gibt
und ist dann auch sehr einfach zu formulieren.
Also die Idee bei der binären Suche ist, dass wir das gesuchte Element
sozusagen einschließen durch eine linke und rechte Schranke.
Und die Invariante sagt im Wesentlichen, das gesuchte Element ist
irgendwo zwischen L und R.
Genauer gesagt habe ich hier die Invariante, dass 0 kleiner gleich L,
kleiner R, kleiner gleich n plus n ist.
Also die sind alle im sinnvollen Bereich.
Also links ist wirklich links von rechts.
Und die sind kein Out-of-Bound-Ding.
Und AL ist echt kleiner als der Schlüssel und AR ist größer oder
gleich der Schlüssel.
Das meine ich hier mit dem Eingeschlossensein.
Diese Invariante wird etabliert durch diese Zuweisung LR gleich 0 n
plus 1.
Also ich bleibe auf der sicheren Seite.
0 ist minusunendlich, AN plus 1 ist plusunendlich, der gesuchte
Schlüssel liegt sicherlich dazwischen.
Der Trick bei binärer Suche ist einfach, wir bestimmen jeweils ein
Mittelelement R plus L halbe.
Und dann gibt es zwei Fälle, wenn der gesuchte Schlüssel kleiner
gleich AM ist, dann sagt uns die Invariante, wir können ohne Bedenken
das AR auf M setzen.
Wir wissen, alles danach ist größer gleich.
Dieser Teil der Invariante gilt auch.
Der gilt auch weiterhin, weil sich AL ja nicht geändert hat.
Umgekehrt, wenn das nicht stimmt, dann heißt das ja K größer AM.
K größer AM, das heißt wir können AL durch AM ersetzen oder einfach L
durch M ersetzen.
Da der Abstand zwischen L und M sich jedes Mal halbiert, brauche ich
hier nur logarithmische Zeit.
Eine andere Übungsaufgabe wäre, dass Sie ein etwas anderes Interface
hier machen, dass Sie zwei Zahlen zurückgeben, die alle Vorkommen
eines Schlüssels einschließen, wenn in diesem reinen Schlüssel
mehrfach vorkommen darf.
So wie das hier programmiert ist, müsste man sich eigentlich mal
überlegen, was man da genau bestimmt.
Ich denke mal bestimmt, das erste Element, das größer gleich ist, ist
ja die Spezifikation vom Locate.
Mal gucken, ob das auch stimmt.
Wenn zum Beispiel alle gleich sind, ganz interessanter Fall, M ist
irgendwo mittendrin, sind aber alle gleich, dann steht hier K kleiner
gleicher M, das stimmt, dann wird R auf M gesetzt, aber L wird nie
geändert und das bleibt auch so.
Dann finde ich das Erste.
So, habe ich schon gesagt, Zeit ist O von Log N.
Machen wir nochmal ein Beispiel.
Wir suchen K gleich 15 in diesem Array mit diesen Indizes.
Am Anfang ist L und R 0 und 9, also N plus 1.
0 plus 9 ist 9, halbe ist 4, also ist M gleich 4.
Das ist hier die 7, die ist kleiner der 15, deshalb setze ich L auf 7.
Jetzt ist mein Bereich dieser hier.
7 ist in der Position 4, plus 9 ist 13, durch 2 abgerundet ist 6, also
ist die Mittelposition jetzt hier.
13 ist auch kleiner 15, also wandert das L hier hin.
6 plus 9 ist 15, durch 2 ist 7,5, also ist mein M jetzt hier.
Jetzt ist aber K kleiner 17, also setze ich R auf die Position 7.
Und jetzt habe ich tatsächlich die Abbruchbedingung L plus 1 ist
gleich R.
Und die Invariante sagt mir, naja, AL kann jetzt nicht die Antwort
sein, weil AL ist echt kleiner dem Schlüssel.
Also muss es R sein.
Und damit habe ich mein Ergebnis 17, das ist hier durch diese
Unterstreichung angegeben.
Fragen zur binären Suche noch?
So, und was uns hier eigentlich interessiert, ist eine Dynamisierung
dieser sortierten Array-Datenstruktur.
Das heißt, wir wollen insbesondere die Operationen Element einfügen,
Element löschen, Update, einschließlich einer Schlüsseländerung, und
eben dieses Locate.
Und die wollen wir alle in logarithmischer Zeit unterstützen.
So, und dann gibt es noch eine ganze Reihe weiterer Operationen für
sortierte Folgen, die man in verschiedensten Anwendungen braucht.
Relativ simpel, erstes Listen-Element, letztes Listen-Element sind
dann ja das kleinste und größte Element.
Das kann man, wenn man es darauf anlegt, auch in konstanter Zeit
machen.
Im Wesentlichen, indem man sich merkt, wo Anfang und Ende der Liste
sind.
Spannendere Operation ist Range-Search.
Ich will jetzt alle Elemente haben, deren Schlüssel zwischen zwei
Grenzen A und B liegt.
Und da will ich gleich mal die Implementierung vorstellen, die zeigt,
dass dieses Locate einem eigentlich schon sehr viel weiterbringt.
Zumindest, wenn wir diese Repräsentation haben, dass die Liste unten
nochmal als doppelt verkettete Liste repräsentiert ist.
Dann brauchen wir nämlich nichts anderes machen, als ein Locate von A.
Ergebnis wird auf leer initialisiert.
Das heißt zum Beispiel, wenn ich alle Elemente zwischen 12 und 20
haben will, dann mache ich ein Locate von 12, kriege hier die 13.
Und dann laufe ich halt durch die Liste, solange ich Elemente kleiner
gleich B sehe.
Ich weiß, das Locate liefert mir das erste Element größer gleich A,
damit ist dieses Constraint größer gleich A erfüllt.
Alles rechts davon ist größer gleich A.
Das heißt, solange das Element, das ich gerade sehe, auch noch kleiner
gleich B ist, kann ich es in das Ergebnis reinschieben.
Die Laufzeit davon ist so von Log N plus Ergebnisgröße.
Und in gewisser Weise geht das nicht besser.
Man nennt übrigens so eine Laufzeit hier auch Ausgabesensitive oder
Output Sensitive im Englischen.
Also wir haben eine Laufzeit, die nicht nur von den Eingabeparametern
abhängt, sondern auch von den Ausgabeparametern.
Und was man da eben ganz oft haben will, ist, dass die Laufzeit
irgendwie linear ist in der Größe der Ausgabe.
Und in gewisser Weise geht das nicht besser.
Und dann will man Größe der Ausgabe plus irgendwas, was schnell ist.
Und in gewisser Weise ist das hier jetzt das Beste, was man sich da
vorstellen kann.
Fragen zu den Operationen bisher und was eine sortierte
Listendatenstruktur tut.
Es gibt noch weitere Operationen Aufbau, wobei insbesondere
interessant ist, wenn man einen Aufbau von einem Konstruktor hat, dem
man schon eine sortierte Liste gibt, zum Beispiel hier so eine doppelt
verkettete Liste, und dann sagt, jetzt will ich die
Navigationsdatenstruktur dazu noch aufbauen.
Und das geht dann, wenn man es richtig macht, in linearer Zeit.
Was halt besser ist, als der naive Ansatz, N Einfügeoperationen zu
machen, wofür man dann ja O von N Log N Zeit brauchen würde.
Dann gibt es noch zwei wichtige Operationen, die ganze Listen
verarbeiten.
Einmal Konkatenieren, also Listen W bis X und Y bis Z.
Unter der Annahme, dass tatsächlich das X kleiner gleich dem Y ist,
darf man die ja konkatenieren.
Und das kann man, wenn man es richtig macht, in logarithmischer Zeit
oder umgekehrt aufspalten.
Man hat eine sortierte Liste, definiert eine Position Y und sagt, ich
möchte alles bis vor das Y als eigene Liste haben und alles ab Y.
Also das hier sind Operationen, die für die doppeltverketteten Listen,
kennen wir das schon, das sind Spezialfälle unserer Splice
-Operationen.
Aber die Schwierigkeit besteht halt darin, diese
Navigationsdatenstrukturen ebenfalls zusammenzubauen bzw.
auseinanderzuspalten.
Wir werden es nicht sehen, aber ich werde darauf hinweisen, dass es in
logarithmischer Zeit geht und auch eine grobe Idee liefert, wie man
das macht.
Die Details stehen im Buch, sind aber doch ein bisschen komplizierter,
als ich es für Algorithmen 1 mir leisten möchte.
Weitere Operationen, die man manchmal sieht, haben irgendwas zu tun
mit Anzahlelemente.
Rank, Select und Range Size, muss ich noch erklären, was das ist.
Also wenn ich ein Element in der Liste habe, zum Beispiel das hier,
möchte ich wissen, dass wieviel der Element ist es.
Bei einem Array wäre das irgendwie offensichtlich, aber bei einer
verketteten Liste ist das zunächst mal nicht so einfach.
Dass das 1, 2, 3, 4, hier das fünfte Element ist, die 11, das muss man
irgendwie ausrechnen.
Aber auch das kann man in logarithmischer Zeit, wenn man die
Datenstruktur geeignet aufbohrt, sage ich mal.
Select ist so ähnlich, ich gebe eine Position vor und möchte das so
und sovielte Element haben.
Zum Beispiel Select 3 wäre das fünfte Element.
Das ist übrigens der gleiche Begriff für Select, wie wir ihn letzte
Woche kennengelernt haben für unsortierte Folgen.
Wo man sagt, ich will das Element mit einem gegebenen Rang haben.
Das war bei unsortierten Folgen, braucht man dafür Linearzeit.
Mit diesem Quick-Select-Algorithmus.
Hier, weil die Folge bereits sortiert ist, geht das schneller in
logarithmischer Zeit.
Dann schließe ich noch Range Size.
Wenn ich so eine Range-Query mache, habe ich Laufzeit proportional zur
Ausgabegröße.
Vielleicht will ich ja gar nicht explizit eine Liste aller Treffer
haben, sondern nur wissen, wie viele das sind.
Die zählen und das geht noch schneller in logarithmischer Zeit.
Fragen zu diesen fortgeschrittenen Operationen auf sortierten Folgen?
Jetzt können wir das mal abgrenzen zu anderen Datenstrukturen zur
Verwaltung von Mengen, die wir schon gesehen haben.
Cache-Tabellen unterstützen nur die Operationen Einfügen, Löschen und
Suchen.
Und man sollte jetzt sehr gut unterscheiden zwischen dem Find und dem
Locate.
Kann mir jemand sagen, was der Unterschied ist?
Wenn ich hier diese Menge von Elementen habe, was kommt raus, wenn ich
sage Find 13?
Nein, sagen wir Find 12, was kommt raus?
Was kommt raus?
Ja.
19?
Genau, wenn ich sage Locate 12, kommt 13 raus.
Was kommt raus, wenn ich meine Hashtabelle sage, die diese Elemente
enthält, Find 12?
Was kommt dann?
Da kommt nichts dabei raus, der sagt, nö, ist nicht da.
Aber der Trick ist, manchmal will man nicht nö, ist nicht da hören,
sondern nö, ist nicht da, aber das nächstgrößte ist die 13.
Das ist also eine durchaus andere Funktionalität und wir werden auch
Beispiele vorstellen, warum man das braucht.
Genau,
ein anderer Grund, woran man schon sieht, dass das ein Unterschied
ist, ist diese Operation Range Query.
Gib mir alle Elemente zwischen A und B, das kann man mit einer
Hashtabelle nicht machen.
Weil dann sage ich zum Beispiel Find A und dann sagt er, nö, ist nicht
da, B ist auch nicht da, aber ich habe keinerlei Information darüber,
was dazwischenliegt.
Und das geht nur, wenn ich tatsächlich so eine Anordnung der Elemente
habe.
Das ist vielleicht deshalb eine der wichtigsten Operationen, die
wirklich einen Unterschied liefert zu der Hashtabelle.
Aber mir passiert es immer wieder, dass meine Bachelor- und
Masterarbeiter kommen und sagen, ich brauche hier so eine Set
-Datenstruktur.
Da habe ich die STL-Implementierung für Set genommen, das ist
einigermaßen schnell, braucht aber trotzdem 80% der Laufzeit.
Und ich sage, nein, sie brauchen keine Set-Datenstruktur, sie brauchen
eine Hashtabelle.
Und dann wird es plötzlich alles viel schneller.
Da muss ich schon genau überlegen, brauche ich wirklich diese Art
Operationen und wenn nein, ist eine Hashtabelle oft effizienter.
Genauso sortiertes Feld, da kann ich halt keine Update-Operationen
machen.
Oder genauer gesagt, Updates sind sehr teuer und das lohnt sich in
vielen Fällen nur, wenn man so Bulk-Updates macht.
Also was weiß ich, ich habe n Elemente und ich füge dann n halbe neue
Elemente ein oder lösche ganz viel.
Und das kann dann effizienter sein als so eine volldynamische
Datenstruktur.
Aber wenn die Anwendung wirklich sagt, ich möchte einzelne Elemente
einfügen und löschen, dann ist so eine sortierte Folgendatenstruktur
effizienter.
Prioritätslisten sind auch volldynamisch, unterstützen aber eben nur
ein begrenztes Spektrum von Operationen, nämlich Insert, Delete, Min.
Und vielleicht noch hier Decrease Key oder Remove bei den
Adressierbaren.
Und da ist das so, eigentlich können Sie eine Prioritätsliste auch mit
sortierten Folgen machen, die sind eine stärkere Sache, weil wie
gesagt Minimum bestimmen ist ja das erste Element in dieser Liste.
Einfügen können Sie auch, löschen können Sie auch.
Dann können Sie auch Delete, Min machen, indem Sie das Minimum nehmen
und löschen.
Geht alles in logarithmischer Zeit.
Asymptotisch ist das genauso schnell wie Binary Heaps zum Beispiel.
Der Trick ist aber, dass die konstanten Faktoren bei Prioritätslisten
ein bisschen kleiner sind.
Und aus theoretischer Sicht, dass bestimmte Operationen wie Decrease
Key oder Merge in Prioritätslisten noch effizienter implementierbar
sind.
Auch asymptotisch effizienter als in der allgemeineren sortierten
Listendatenstruktur.
Also Decrease Key werden wir in Algorithmen 2 sehen, geht bei
Prioritätslisten in konstanter Zeit.
Während sortierte Folgen dafür logarithmische Zeit brauchen.
Das Merge geht auch in konstanter Zeit, während sortierte
Folgendatenstrukturen dafür lineare Zeit brauchen.
Insgesamt könnte man sagen, sortierte Folgen sind sowas wie die
eierlegende Wollmilchdatenstruktur.
Die können fast alles, sind aber für die einzelnen Operationen
meistens ein bisschen langsamer als speziellere Datenstrukturen.
Man könnte auch diesen Spruch sagen, wenn Sie irgendwie auf eine Insel
gehen müssten und müssten da programmieren, dürften aber eine
Algorithmenbibliothek mitnehmen, in der nur eine einzige Datenstruktur
implementiert ist.
Dann könnten Sie sich überlegen, diese sortierten Folgen zu nehmen,
weil damit kann man fast alles machen.
So, Anwendungen.
Wir werden ein Beispiel sehen für eine Best-First-Heuristik.
Also wieder Gridi-Algorithmus.
Ich treffe punktuelle Entscheidungen, um schrittweise mein Problem zu
lösen und mache jeweils die lokal am besten aussehende Entscheidung.
Wir werden den Algorithmen 2 sehen.
Algorithmische Geometrie.
Da gibt es zum Beispiel Algorithmen, die Sweep-Line-Algorithmen
heißen.
Da nimmt man meist zwei-dimensionale Algorithmen, nimmt eine vertikale
Linie, die man über eine Menge von Objekten drüber sweepen lässt, also
wischen sozusagen.
Und immer wenn dann diese Linie ein Objekt trifft, muss man bestimmte
Operationen machen.
Und dafür muss man Hilfsdatenstrukturen verwenden, die sozusagen die
Menge der Objekte verwaltet, die diese Sweep-Line gerade schneiden.
Und dafür benutzt man sortierte Folgendatenstrukturen.
Oder Datenbanken haben Index-Datenstrukturen, die sehr oft solche
sortierten Folgendatenstrukturen sind.
Und vieles anderes mehr.
Fragen zu Anwendungen?
So, jetzt will ich mal eine dieser Anwendungen vorstellen, damit man
mal ein konkretes Beispiel sieht, wo man gerade dieses Locate braucht.
Und zwar ist das eine Heuristik für Binpacking.
Also Sie haben Objekte vorgegebener Größe, die Sie in Kartons packen
sollen.
Und Sie wollen möglichst wenig Kartons brauchen.
Also stellen Sie sich vor, Sie haben irgendwie ein Riesenlagerhaus
voller Pakete, die Sie, sagen wir, das sind Hilfspakete für irgendein
Überschwemmungsgebiet, die Sie da halt verschiffen wollen in dieses
Katastrophengebiet.
Und Sie zahlen halt pro Container, den Sie verwenden.
Und nehmen wir mal an, die Pakete sind ziemlich schwer, also Volumen
ist kein Problem, es geht nur um das Gewicht der Pakete.
Und jetzt müssen Sie sich überlegen, also wie viele Container brauche
ich?
Und dafür muss man geschickt die Pakete in die Container packen, damit
Sie möglichst wenig brauchen.
Das ist ein bekanntes kombinatorisches Optimierungsproblem, das
natürlich in der Praxis dann manchmal noch zusätzliche
Seitenbedingungen hat, aber trotzdem gibt es auch konkrete
Anwendungen, die genau das brauchen.
Und was man da macht, ist zunächst mal sortiert man die Elemente nach
absteigender Größe, also es ist immer eine gute Idee, die großen
Objekte zuerst zu positionieren, weil die sozusagen schwierig zu
positionieren sind.
Man hält eine Liste von geöffneten Containern, also Container, wo man
bereits gesagt hat, die brauche ich, und hat aber dann für jeden
Container vielleicht noch eine Restkapazität.
Die ist am Anfang die Gesamtkapazität der Container und schrumpft dann
in dem Maße, wie man da Elemente einfügt.
Jetzt gehe ich durch meine Pakete nach absteigendem Gewicht.
Und dann, wenn es keinen offenen Container gibt mit einer
Restkapazität größer dem Gewicht von dem Objekt, oder größer gleich,
müsste ich hier schreiben, dann füge ich einen neuen Container hinzu,
der komplett leer ist.
So, diese Containerliste verwalte ich als sortierte Liste, und zwar
sortiert nach der Restkapazität.
Und best fit ist jetzt die Heuristik, die sagt, wenn ich an dieser
Stelle bin, weiß ich, es gibt mindestens einen Container, der mein
Objekt aufnehmen kann, und ich suche mir den mit der kleinsten
Kapazität, der ihn trotzdem noch aufnehmen kann.
Das nennt man best fit, also man lässt möglichst wenig Luft.
Die Hoffnung ist, dass man dann irgendwann einen Container findet und
ein Element das Ding genau ausfüllt, und dann hat man den irgendwie
super effizient benutzt, und das ist in der Praxis eine ganz gute
Heuristik, und man kann sogar was darüber zeigen, wie viel Platz man
braucht, und das ist relativ wenig.
Und wenn man sich das überlegt, ist das genau diese Locate-Operation.
Also ich suche in dieser sortierten Liste genau das kleinste Element
mit einer Reservoir-Kapazität, größer gleich dem Gewicht, das man im
Paket hat.
Dann füge ich dieses Element ein, und das bedeutet, dass ich die
Kapazität von diesem Container verringere, und das wird dann entfernt
und an einer anderen Stelle neu eingefügt.
Oder eben eine kombinierte Operation, die ein Update des Schlüssels
macht.
Laufzeit ist O von Anzahl Pakete, Log-Anzahl Pakete für das Sortieren.
Diese Container-Liste ist auch höchstens O von Anzahl Pakete lang.
Die Operationen brauchen logarithmisch in der Länge der Liste, also
insgesamt O von S, Log-S.
Gibt es dazu Fragen?
Ja,
das sollte größer gleich E sein.
Weitere Fragen?
Gut, das ist auch ein typisches Beispiel für einen Greedy-Algorithmus,
ein typisches Beispiel für einen Scheduling-Algorithmus usw.
So, jetzt habe ich viel darüber gesagt, dass es schön ist, so eine
Datenstruktur zu haben.
Jetzt wollen wir uns dem langsam annähern, wie man das wirklich
implementiert.
Am Ende werden wir die wahrscheinlich komplizierteste Datenstruktur
haben, die wir im Laufe dieser Vorlesung kennenlernen, weil man da ein
paar Sachen falsch machen kann und die Sachen richtig machen, macht es
nicht einfacher.
Das kann ich Ihnen leider nicht komplett ersparen.
Aber ich denke, die Grundlagen sind doch immer noch relativ einfach.
Also wir lernen jetzt zunächst mal im Prinzip einen sehr einfachen
Ansatz, kennen binäre Suchbäume, mit denen man diese sortierten Folgen
implementieren kann.
Also meine Navigationsdatenstruktur ist jetzt ein Binärbaum.
Das ist jetzt die erste wichtige Entwurfsentscheidung.
Und die Blätter dieses Binärbaums sind im Prinzip meine
Listenelemente.
Und die inneren Knoten sind die Navigationsdatenstruktur.
Also die eigentlichen Elemente sind in der Variante, die ich
vorstelle, in diesen Blättern gespeichert.
Die Navigationsdatenstruktur enthält nur Schlüssel.
Da gibt es aber auch andere Varianten.
Die Datenstruktur-Invariante ist halt meine inneren Knoten enthaltenen
Schlüssel und Verweise auf den linken und rechten Teilbaum.
Die Invariante ist, dass alle über den linken Verweis erreichbaren
Blätter einen Schlüssel kleiner gleich K haben und alle über den
rechten Verweis erreichbaren Blättern einen Schlüssel größer K haben.
Und hier ist jetzt halt mal ein Beispiel.
Wir haben diese Liste 2, 3, 5, 7, 11, 13, 17, 19.
Das sind die Primzahlen kleiner gleich 20.
Und man könnte jetzt verschiedene Navigationsdatenstrukturen
hinschreiben, die diese Invariante erfüllen.
Ich habe jetzt halt mal diese hier gewählt.
Die Wurzel hat den Schlüssel 17.
Es ist jetzt tatsächlich so, dass die 17 hier auch erreichbar ist von
links und das nächste Element aber nicht mehr.
Das ist die Invariante.
Es könnte aber zum Beispiel auch sein, dass das hier eine 18 hat,
obwohl die hier unten nie auftritt.
Das ist ein wichtiges Detail, das Sie sich merken sollen.
Das verlangt meine Invariante nicht, dass diese Spaltelemente
tatsächlich unten auftreten.
Das wird dann wichtig, wenn man Elemente löschen will, zum Beispiel.
Also Invariante ganz einfach.
Jetzt mal ein paar allgemeinere Bemerkungen zu Varianten und
Suchbaumdatenstrukturen.
Dieses Dummy-Element, das wir haben, das wird in den meisten
Implementierungen nicht verwendet, ist im Prinzip vermeidbar.
Entschuldigung.
Aber das ist ein bisschen so ähnlich wie bei den verketteten Listen
auch.
Die Gegenwart des Dummy-Elements erlaubt mir, meine Prozeduren etwas
einfacher zu formulieren.
Oft ist es auch so, dass die Implementierung die Elemente nicht in den
Blättern speichert, sondern auch an den inneren Knoten.
Dann hätte man sowas zum Beispiel.
Die 17 wäre direkt hier an der Wurzel gespeichert und nirgendwo
anders.
Also das ist jetzt die gleiche Menge von Objekten in so einem Baum,
der das direkt in den inneren Knoten speichert.
Das hat Vor- und Nachteile.
Ich finde es aber konzeptuell einfacher, die Liste zu trennen von der
Navigationsdatenstruktur.
Vor allem werden dann diese Range-Querys sehr viel einfacher und auch
in gewisser Weise effizienter.
Dann ist es so, in der Informatik-Terminologie wird ganz oft der
Begriff Suchbaum als Synonym für den Begriff sortierte Folge
verwendet.
Also das, was ich hier sortierte Folge nenne, finden Sie in der
Literatur eigentlich ganz selten.
Da gibt es irgendwie keinen richtigen Begriff für.
Eigentlich, weil die Leute da oft Interface und Implementierung
verwechseln und dann lieber Suchbaum sagen.
Aber das haben wir von Anfang an schon gesagt, das ist eine
Unsauberkeit, die zu Verwirrungen führen kann.
Deshalb versuche ich das hier sauber zu trennen.
Also insbesondere gibt es halt Datenstrukturen für sortierte Listen,
die überhaupt nichts mit Bäumen zu tun haben.
Deshalb kann man den Begriff Suchbaum eigentlich nicht verwenden.
Zum Beispiel ein Karteikasten hat nichts mit Bäumen zu tun.
Und man kann diesen Karteikasten eigentlich wieder auf so ein
sortiertes Array mit Löchern abbilden.
Da gibt es interessante Arbeiten darüber, die zeigen, dass das
eigentlich eine ziemlich gute Idee ist.
Aber das kann man nicht als Suchbaum bezeichnen.
Deshalb sollte man sich da vorsichtig sein.
Oder es gibt sogenannte Skip-List-Datenstrukturen.
Da haben Sie eine verkettete Liste und dann verkürzte Versionen dieser
Liste, die übereinander gestapelt sind.
Das sind auch keine Bäume.
So, dann gucken wir uns jetzt mal die Locate-Operation an in diesen
binären Suchbäumen.
Die Idee ist ganz einfach.
Ich benutze halt die Spaltschlüssel als Wegweiser.
Ich mache es erstmal an einem Beispiel.
Ich suche das Element mit dem Schlüssel 15 oder das nächstgrößere.
Ich fange an der Wurzel an und die sagen, naja, also hier, alles bis
17 findest du eigentlich links.
Ja, dann gehe ich doch links.
Und dann bin ich hier bei der 7 und die sagen, ja, alles bis 7 findest
du links.
Alles größer 7 findest du rechts.
Ja, aber 15 ist größer 7, also gehe ich nach rechts.
Genauso hier, 15 ist größer 13, gehe ich nach rechts und habe die 17
gefunden.
Prima.
Wie gesagt, das könnte auch anders sein, wenn ich die 18 suche und
hier auch die 18 stehen habe, würde ich den gleichen Pfad runtergehen,
lande aber bei der 17.
Also muss ich ein bisschen aufpassen.
Es könnte auch sein, dass mein Element das nächste ist.
Also das sind die beiden Varianten und das ist, was ich dann
rauskriege als Pseudokod.
Also wenn x ein Blatt ist, dann muss ich diese beiden Varianten hier
unterscheiden.
Wenn k kleiner gleich x, dann gebe ich das zurück.
Sonst ist k größer x, dann wäre das falsch, das x zurückzugeben, also
gebe ich das nächste zurück.
Und wir werden zeigen, dass das dann auch korrekt ist.
Ansonsten, wenn es kein Blatt ist, wenn k kleiner gleich x, gehe ich
nach links und sonst nach rechts.
Fragen zu dem Pseudokod für Locate?
So, jetzt Invariante mache ich noch.
Erkläre ich noch, wie das Locate geht, brauche ich noch etwa 5
Minuten.
Und die anderen Operationen mache ich beim nächsten Mal.
So, jetzt habe ich so mit Händewedeln gesagt, dass das korrekt ist.
Tatsächlich ist es so, dass das, glaube ich, im Buch falsch ist.
Da haben wir die falsche Invariante.
Offenbar ist es also nicht so trivial.
Deshalb will ich das jetzt mal genauer erklären.
Was ist denn überhaupt die Schleifeninvariante, bzw.
die Invariante, die ich in dieser Rekursion für Locate habe?
Und wie folgt daraus die Korrektheit von der Locate-Funktion?
Also Locate kriegt ja neben dem Schlüssel einen Verweis auf einen
inneren Knoten.
Oder einen Knoten dieses Suchbaums.
Und der ist Wurzel eines Teilbaums.
Und die Invariante sagt im Wesentlichen,
alles, was nicht in diesem Teilbaum ist, aber weiter links, ist echt
kleiner als K.
Alles, was nicht in dem Teilbaum ist, aber weiter rechts, ist echt
größer.
Alles, was von links erreichbar ist, ist kleiner gleich K.
Und alles, was von rechts über X erreichbar ist, ist größer X.
Also ich habe hier einen Spaltschlüssel X.
Und alles, was nach links erreichbar ist, ist kleiner gleich X.
Das ist schon diese Invariante.
Und alles, was nach rechts erreichbar ist, ist größer X.
Und alles, was da nicht erreichbar ist, also weiter oben nach rechts
erreichbar ist, ist größer K.
Und was weiter links steht, ist kleiner K.
Das gilt sicherlich am Anfang.
Also wenn ich die Wurzel habe, dann ist das gerade die Datenstruktur
-Invariante.
Und alles, was da nicht drin ist, das sind diese Dummies,
minusunendlich, plusunendlich.
Also am Anfang stimmt es.
Dann, wenn ich hier nach...
Also jetzt diese beiden Dinger...
Also wenn ich das hier gegeben habe, zu meinem jetzigen Zeitpunkt, und
K ist kleiner gleich X, dann weiß ich ja, alles, was hier erreichbar
ist, ist größer gleich X.
Und damit erst recht...
Alles, was hier rechts ist, ist größer X.
Und damit erst recht größer K.
Das heißt, ich kann das sozusagen rechts liegen lassen und nach links
absteigen.
Und genauso, wenn ich hier hingehe, ich weiß jetzt, K ist größer X.
Das heißt, alles, was hier links ist, ist echt kleiner als K.
Deshalb kann ich das links liegen lassen und nach rechts absteigen.
Und die Ergebnisberechnung muss man noch ein bisschen genauer wissen.
Wenn ich an einem Blatt bin, dann ist die Invariante halt nichts
anderes als das hier.
Ich bin an einem Blatt.
Hier ist mein Schlüssel X.
Und jetzt einfach eine Spezialisierung davon.
Das links ist kleiner und das rechts ist größer.
Also alles, was hier links ist, ist kleiner K.
Alles, was rechts ist, ist größer K.
So, und jetzt gibt es drei Fälle.
Entweder K gleich X.
Dann würde ich das auch zurückgeben.
Und das passt auch, weil wenn es gleich X ist, dann gilt insbesondere
K kleiner gleich X.
Und ich gebe das zurück.
Also in dem Fall bin ich korrekt.
Wenn K kleiner X, gilt das hier auch.
Ich weiß, das, was ich dann zurückgebe, ist größer als X.
Ich weiß außerdem, das Ding selber ist nicht drin, weil alles, was
links ist, ist echt kleiner.
Und das will ich garantiert nicht zurückgeben.
Also bin ich auch korrekt.
So, und wenn jetzt der dritte Fall eintritt, K ist größer X, dann gebe
ich das nächste zurück.
Und das ist korrekt, weil, naja, ich weiß, das ist größer K.
Das erfüllt also das, was ich haben will.
Das K selber gibt es nicht.
Sonst wäre der Fall eingetreten.
Und da links sind alles Sachen, die kleiner sind als K, die
interessieren mich nicht.
Also habe ich da auch das korrekte Ergebnis.
Aber man muss diese Fälle unterscheiden, damit wir mit unserer
Datenstrukturinvariante zu einem korrekten Locate kommen.
Ja, Laufzeit.
Die gute Nachricht ist, das ist einfach zu analysieren.
Das ist konstante Zeit pro Schicht des Baums, die ich durchlaufe.
Also O von Höhe dieses Baums.
Im besten Fall ist die logarithmisch.
Das ist das, was ich haben will.
Leider, im schlechtesten Fall könnte der komplett degeneriert sein zu
so einer Liste.
Und dann habe ich Höhe N und das ist nicht effizienter, als in einer
verketteten Liste Dreck zu suchen.
Und beim nächsten Mal werden wir halt sehen, wie man dafür sorgen
kann, dass dieser schlechteste Fall nicht auftritt.
Und man wirklich immer mit O von Log N-Schritten rauskommt.
Fragen dazu zum Locate?
Gut, dann alles Weitere beim nächsten Mal.
Dankeschön.
Okay, dann willkommen zur Übung.
Und, Übung fehlt noch.
Genau, wir machen nahtlos quasi weiter.
Mit binären Suchbäumen gleich.
Aber vorher noch ein paar Kommentare zu dem Sortieralgorithmen
-Kapitel.
Ganz am Anfang der Vorlesung hat mir mal eine E-Mail geschrieben und
mich gefragt, warum gibt es denn so viele Sortieralgorithmen?
Naja, jetzt habt ihr ein paar kennengelernt und warum benutzt man
nicht nur genau eine von denen?
Weil eine ist doch besonders gut.
Dann beantwortet mir mal die Frage, welche von den vielen wärs denn
eigentlich?
Die haben alle unterschiedliche Eigenschaften, natürlich.
Und was wir auch immer ausrechnen in der Analyse, sind die Anzahl von
Swaps oder die Anzahl von Schreibvorgängen, die Anzahl von
Vergleichen.
Und je nachdem, wie teuer diese Operationen sind, sind halt
unterschiedliche Algorithmen die besten.
Das ist die Sache.
Beispielsweise gibt es einen, der eine minimale Anzahl von
Schreibvorgängen hat.
Und der ist dann beispielsweise gut, wenn Schreibvorgänge unglaublich
teuer sind.
Was weiß ich, bei EEPROMs oder SSDs oder so.
Und deswegen gibt es halt nicht die Patentlösung.
Das andere ist natürlich auch, dass die ganzen Analysen von den
Sortieralgorithmen als solches sehr interessant sind und lehrreich
sind.
Deswegen gibt es nicht nur einen hier in der Vorlesung.
Dann habe ich noch ein paar Sachen zu der Programmieraufgabe.
Da wurden wir gefragt, ob ihr die Listen oder Array-Datenstrukturen
von Java verwenden dürft.
Das könnt ihr gerne machen.
Ich kann es aber nicht empfehlen, weil die fürchterlich langsam sind.
Kann man aber natürlich mal verwenden und dann nachher ersetzen oder
so.
Also ihr seid da frei.
Machen, was ihr wollt.
Dann habe ich noch einen Nachtrag zum Übungsblatt, was übermorgen
fällig ist.
Nur ein kleiner Hinweis zu dieser Aufgabe.
Ich habe als Student immer solche Aufgaben gehasst, wo die Leute sich
irgendwas ausgedacht haben, damit ihr das analysieren müsst.
Und dann fürchterlich viele Schwierigkeiten reingebaut habt, dass die
Aufgabe irgendwie hirnrissig schwierig ist.
Dem ist nicht so.
Das ist echter Kot, den wir irgendwo gefunden haben.
Und was ihr da jetzt in der Übungsaufgabe macht, ist, was viele
Informatiker auch im Berufsleben machen, ist einfach ein Code-Review.
Man muss halt angucken, ist das jetzt richtig, was der Kollege da
geschrieben hat?
Okay, also das ist nicht, um euch zu ärgern, entstanden, sondern weil
das tatsächlich irgendwo her ist.
Okay, dann geht es jetzt los.
Wir hatten jetzt gerade die ganze Zeit Suchbäume und ich möchte mit
euch ein wenig in Suchbäumen rechnen.
Genau, dazu einfach mal einen Suchbaum malen.
Wurzel ist rot bei mir.
Ein bisschen rechnen da drin, Wurzel.
Ein kleiner Suchbaum.
Ein paar Knoten rein und dann noch eine Ebene Blätter für den Baum.
Und Kanten dazwischen.
Wie viele Knoten hat mein Baum?
Wir wollen jetzt so ein bisschen entwickeln, was die Kennzahlen von so
einem Baum sind.
In der Realität sind die natürlich nicht immer vollständig, aber für
das Beispiel rechnen wir quasi die schlimmstmögliche Kombination.
Alle anderen sind kleiner.
Also wir haben in unserem Baum immer N Knoten, also zumindest nennen
wir die mal die Anzahl der Knoten N.
Und in unserem Beispiel sind das wie viele?
Wer möchte zählen?
Es sind 15.
Zumindest hoffe ich das.
Dann gibt es die wichtige Kennzahl von den ganzen binären Bäumen, die
ist immer die Höhe.
Warum?
Die Höhe wird nachher die Komplexität von den ganzen Algorithmen
festlegen.
Da steht dann immer U von H.
Das ist die Höhe.
Was die tatsächliche Höhe von unserem Baum hier ist, das lasse ich
jetzt gerade mal offen.
Jetzt überlegen wir uns mal gleich, was wir da am besten
hindefinieren.
Aber was klar ist, ist die Anzahl der Blätter.
Und Blätter sind blau, weil Blätter sind blau.
Aber davon weiß ich, das sind acht.
Und der Rest, die nennen wir dann innere Knoten.
Wurzel gibt es nur eine.
Davon gibt es natürlich sieben.
Okay, was wissen wir über unseren...
Ah ja, was ist denn das für ein Baum?
Den nennt man perfekten Baum.
Man ist irgendwie dazu geneigt, den vollständig zu nennen.
Der ist auch vollständig.
Diese Nomenklatur ist ein bisschen uneinheitlich.
Manche nennen den schon vollständig, manche nennen den, weil perfekt
ist irgendwie ein komischer Begriff.
Was ist denn da jetzt daran perfekt?
Ja, das ist ein Perfekter für uns.
Und der ist deswegen also vollständig.
Gibt es auch.
Genau, dieser Perfekte Baum ist perfekt, weil in jeder Ebene quasi
zwei hoch i Knoten sind.
Also beispielsweise hier in der Ebene sind acht, hier sind es vier, da
sind es zwei, da sind es einer.
In jeder Ebene zwei hoch i Knoten.
Zum Beispiel ist unsere Blattebene zwei hoch drei.
Nämlich acht.
Und aus dieser Motivation kommt dann eigentlich auch die Definition
der Höhen.
Hier ist quasi Ebene drei, weil da zwei hoch drei Knoten drin sind.
Und hier ist zwei, eins, null.
Die Definition liegt hier.
Die Definition, die Höhe muss man natürlich einmal für den Knoten
definieren und einmal für den Baum.
Die Höhe von so einem Knoten ist einfach die Anzahl der Kanten, die
auf dem eindeutig bestimmten Weg von Wurzel zu Knoten liegen.
Das ist einfach die Anzahl der Sprünge, die man hier drin macht.
Ich glaube, dass der richtige Hintergrund darin eigentlich ist, dass
hier zwei hoch i Knoten auf der i-ten Ebene sind.
Und die Höhe von dem ganzen Baum ist halt die maximale Höhe über
Knoten.
Gut.
So, ein bisschen rechnen.
Jetzt können wir nämlich feststellen, wir haben n, das ist ja
schließlich die Summe über alle Ebenen, deswegen summieren wir einfach
über alle Ebenen.
Von null bis, ja genau, h ist nämlich drei im Allgemeinen.
h ist die maximale Tiefe.
Genau, von zwei hoch i.
Und jetzt kennt ihr hier, das da muss euch an was erinnern inzwischen,
das ist nämlich geometrische Reihe.
So, das habe ich komplizierter geschrieben als eigentlich notwendig.
Ja, das war's.
Der vollständige oder perfekte Binärbaum mit Höhe h hat genau zwei
hoch h plus eins minus eins.
Das ist n, meine h's und n's sind ein bisschen schwierig zu
unterscheiden.
Okay, was machen wir daraus?
Die erste Formel, die man da wirklich daraus herleiten kann, ist eine
Formel, die uns interessiert für eigentlich dieses h hier drin.
Denn wenn wir jetzt n Knoten haben, wollen wir eigentlich wissen, wie
lange unsere Algorithmen brauchen, nämlich Höhe.
Und Höhe, wenn wir so ein bisschen hier rechnen, n ist gleich zwei
hoch k plus eins.
Dann stellen wir die eins mal auf die andere Seite, dann haben wir n
plus eins ist zwei hoch.
Versuche mal meine h so zu machen.
Plus eins.
Logarithmieren.
Log mit zwei, weil beides positiv ist, darf ich das machen.
a plus eins.
Und genau, das h wollen wir.
h ist gleich log zwei von n plus eins minus eins.
Das plus minus eins ist ein bisschen hässlich, das gilt ja auch im
Allgemeinen nicht, wenn mein n hier nicht durch den Logarithmus glatt
geht.
Da mache ich dann log zwei, könnt ihr euch mal überlegen.
n abgerundet ist das, was man hier als Höhe eines Baumes haben möchte.
Okay.
So, aber wir können noch ein bisschen mehr rechnen.
Ich wollte hier irgendwo große Umrahmungen machen für die wichtigen
Sachen.
Wir können noch mehr rechnen, und zwar die Beziehung zwischen c und
zwischen der Anzahl der Blätter, der inneren Knoten und der Anzahl der
Knoten ist ja schließlich, ich habe n Knoten insgesamt, davon sind
einige Blätter und einige innere Knoten.
So, jetzt weiß ich aber, dass meine Blätter in dem Fall zwei hoch h
sind.
Zwei hoch h.
Und der Rest ist quasi ja ein kleinerer Baum.
Und deswegen in meinem Baum habe ich hier quasi, der kleinere Baum hat
zwei hoch h minus eins Blätter.
Zwei hoch h minus eins.
Das ist auch ein h.
Okay.
So, was haben wir jetzt da rausbekommen?
Wir haben zwei mal zwei hoch h minus eins, und deswegen können wir uns
noch mal zurückerinnern, das war nämlich b.
Und das ist jetzt eine ganz wichtige Tatsache, die einfach in
Buchstaben hier versteckt ist.
Wenn ich einen Baum habe, der b Blätter hat, dann hat der insgesamt
nur linear viel, nämlich zwei mal mehr minus eins Knoten dann
insgesamt.
Hat nur n minus eins Knoten darüber.
Gucken wir uns das nochmal an.
Wir haben hier acht Blätter und sieben Knoten sind darüber.
Das sind sogar weniger als die Anzahl der Blätter.
Und deswegen funktioniert die Suchdatenstruktur, die Professor Sanders
gerade gezeigt hat, überhaupt.
Deswegen explodiert die nicht, weil die quasi nur gleich viele
Elemente hat, wie Elemente unten drin sind.
Okay, das gleiche kann man auch, jetzt kann man hier nämlich c noch
ableiten, das lasse ich jetzt.
Aber muss man nur umstellen und einsetzen, dann kriegt man die Anzahl
der inneren Knoten.
So, dann überlegen wir uns, das war alles, was ich da dazu machen
wollte.
Genau, wie speichert man sowas?
In der Vorlesung war gerade schon so ein kleines Bildchen.
Das sah so ähnlich aus hier.
Ein paar abgeflachten Teile.
Dass hier halt irgendeine Zahl drin steht und dann zwei Zeiger draußen
sind.
Das ist relativ teure Speicherung, schließlich habe ich für ein
Element noch zwei zusätzliche Zeiger.
In der Vorlesung kommen nachher noch ein paar intelligentere
Datenstrukturen, wo man weniger Zeiger pro Element hat.
Im Prinzip habe ich hier noch mal, ich habe pro Element zwei
zusätzliche Zeiger, anders als im Array, wo ich ja nichts Zusätzliches
irgendwie habe.
Und so muss man sich das dann auch im Rechner vorstellen.
Ich gehe von einem zum nächsten, zum nächsten, zum nächsten und das
ist halt so ein Hin- und Herspringen.
Das ist eine Art zu speichern, die andere kennt ihr auch schon.
Wir machen das jetzt aber mal anders.
Wenn man so einen Baum hat, dann möchte man den meistens traversieren.
Man möchte den Baum durchgehen in irgendeiner Reihenfolge und davon
gibt es eine ganze Menge Reihenfolgen.
Also Traversierungsreihenfolgen, Traversierungsreihenfolgen.
Und die einfachste, ich bekomme die auch immer durcheinander, die
heißt Inorder.
Da besucht man zuerst den linken Teil, dann den Knoten selber und dann
den rechten Teil.
So und jetzt möchte ich hier mal nummerieren.
Jetzt gehen wir mal angucken, wie die Reihenfolge ist, wo wir die
Knoten besuchen.
Das ist der Nullte.
Achso, nein, Entschuldigung, das ist nicht der Nullte.
Wir gehen erst links runter.
Wir gehen zuerst nach links, dann den Knoten selbst und dann nach
rechts.
Das heißt, wir gehen zuerst ganz nach links runter, Nullte, dann den
Knoten selber, dann den zweiten.
Den Knoten selber und so weiter und so fort.
8, 8, 9, 10, 11.
So, 13 und 14.
Kommen da 14 raus, weil ich hier mit Null anfange zu zählen, wenn man
das bei Informatik ab und zu macht.
So, das ist die eine Reihenfolge.
Können wir mal hier hinlegen.
Noch eins.
Hoffentlich.
Die nächste Reihenfolge, die wir uns angucken wollen, ist die
Preorder, die eigentlich auch eine Art natürliche Ordnung ist.
Da besuchen wir erst den Knoten selber, dann den linken und dann den
rechten.
So, wie ihr euch das gerade schon anguckt, da gibt es bestimmt drei
Fakultätmöglichkeiten, hier irgendwie links, rechts und den Knoten
selber anzuordnen.
Und ebenso viele Namen gibt es für Teile.
Das sei jetzt einfach mal so dahingestellt.
Da kann man natürlich sich beliebige Sachen ausdenken, aber den Knoten
selbst, den machen wir noch.
Also, denn das ist irgendwie so das, was man eigentlich machen würde.
Der Knoten selbst, der linke.
So, 4, 5, 6.
Jetzt haben wir mit 1 angefangen.
Na gut, das ist eine komplizierte Sache.
Okay, dann sehen die beiden Nummerierungen halt so aus.
Aber die Preorder ist das, was man sich im Prinzip mal so überlegen
würde.
Ich gehe meinen Baum runter und mache eine Tiefensuche.
Die Tiefensuche kommt bei Grafen nachher, aber bei Bäumen ist das
irgendwie klar, was da passiert.
Tiefensuche in Grafen kommt später noch allgemeiner.
Für uns ist jetzt erst mal die wichtigste, die nennt sich Level Order.
Das ist einfach ebenenweise.
Dann fange ich hier mal bei 0 an.
1, 2, ebenen, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.
So, die kennt ihr schon.
Ist auch eine Art und Weise.
In dem Moment, in dem ich hier quasi Nummern mache, definiere ich auch
implizit Array-Plätze für die Werte in diesem Binärbaum.
Denn das da ist die Art und Weise, wie Heaps abgespeichert werden.
Nämlich in Level Order.
Das da gehen wir zurück.
Das sind die Sachen nochmal in Bund.
Und das hier,
das ist das, was ich euch gerade gezeigt habe, nur mit 1 angefangen zu
zählen.
Da fangen wir mit 1 an zu zählen und dann mache ich das
schichtenweise.
Es gibt auch, wie gesagt, die anderen Traversierungsreihenfolgen,
beispielsweise die Tiefensuche, die Breitensuche, die kommen alle
noch.
Das waren nämlich die beiden, die ich euch gerade gezeigt habe.
Was ich euch gerade gezeigt habe, das ist die Level Order Reihenfolge,
wenn man mit 1 anfängt zu zählen.
Was ich gerade gezeigt habe, ist man fängt bei 0 an.
Denn wenn wir ein Array haben, zumindest in der Regel ist das mit 0
indiziert, das Array.
In der Vorlesung ist der Schritt von einer Ebene auf die nächste 2i
oder 2i plus 1.
Was ist denn der Schritt hier?
Der ändert sich nämlich, aber die Technik bleibt gleich.
Man multipliziert mit 2, in dem Fall plus 1 oder plus 2.
Ganz interessante Sache.
Entweder fange ich mit 0 an zu zählen oder mit 1 an zu zählen.
Die Rechenvorschrift ändert sich natürlich.
Jetzt kann man sich eigentlich eine aussuchen.
Und wenn man sich das überlegt, hier habe ich eine Multiplikation,
eine Multiplikation und eine Addition.
Hier habe ich immer eine Multiplikation und eine Addition.
Kann man also das erste wählen, weil das ein bisschen schneller sein
könnte.
Okay, als Student fand ich dieses ganze Kapitel über Binärbäume
unglaublich verwirrend, weil jetzt kommen auf einmal Binärbäume in
allen Farben und Formen vor und die sehen auch irgendwie immer gleich
aus, immer so schöne Dreiecke.
Aber inhaltlich sind die immer total verschieden.
Die sehen alle gleich aus, aber machen etwas unterschiedliches.
Das Wichtige ist bei diesen Binärbäumen nicht diese Struktur, sondern
die Invarianten, die für diese Zahlen gelten.
Ich habe hier einfach mal Zahlen genommen, das sind im Übrigen beides
die gleichen Zahlen.
Und einmal ist es ein Hieb, ein Max-Hieb und einmal ist es ein binärer
Suchbaum.
Nicht die Form ist wichtig, sondern die Invarianten, die dabei erfüllt
sind.
Und diese Invarianten sind das, was wir dann auch verwenden, um aus
diesem Binärbaum tatsächlich eine nützliche Datenstruktur zu machen.
Die überspringen wir jetzt mal, die Folien.
Das ist nicht ganz so wichtig, Prof. Sanders hat gesagt, es gibt
binäre Suchbäume, manchmal mit Daten in Blättern, manchmal auch mit
Daten innen drin.
Das wechselt so ein bisschen ab.
Eine braucht halt zweimal mehr Platz, aber das ist uns egal.
So, und jetzt bin ich erstmal fertig.
Jetzt kommen noch mehr binäre Bäume mit Sebastian.
Danke, danke.
So, genau.
Wir haben uns ja in der Vorlesung jetzt schon die Min-Hiebs angeguckt.
Was wir jetzt hier nochmal dabei haben, ist ein Max-Hieb.
Im Prinzip ist es das Gleiche, bloß andersrum.
Jetzt ist der Parent nicht mehr kleiner gleich dem Kindknoten, sondern
größer gleich.
Wir haben dann eben Operation, die jetzt Delete Max heißt, die uns das
Maximum aus diesem Baum rauszieht, anstatt ein Delete Min.
Das sei mal nur dahingestellt, das brauchen wir jetzt gleich.
Nämlich für einen Hiebsort, der in place funktioniert, mit einem Max
-Hieb.
In der Vorlesung haben wir ja gesehen, wenn wir einfach einen Min-Hieb
nehmen und da irgendwie Elemente Perl Delete Min rausziehen, dann
schafft man es irgendwie, das Array falschrum sortiert aufzubauen in
place.
Jetzt wollen wir es mit einem Max-Hieb richtig rummachen.
Jetzt zuerst nochmal eine Motivation für diesen Hiebsort.
Da habe ich hier nochmal Selection Sort mitgebracht.
Der wurde auch ganz am Anfang von der Vorlesung angesprochen.
Was macht der?
Er läuft durchs Array durch und sucht immer das kleinste Element,
swappt es dann an den aktuellen Anfang des Arrays und verringert das
Array um eins und läuft dann wieder durch.
Das heißt, wir haben N-Iterationen und pro Iteration muss ich in
linearer Zeit immer das kleinste Element suchen.
Das heißt, wir kriegen für den Algorithmus eine quadratische Laufzeit
und haben aber effektiv so Operationen wie, ich suche das Minimum in
einem Bereich von dem Array und ich entferne dieses Minimum von diesem
Teilbereich von dem Array.
Und wenn ihr euch jetzt diese Operationen anguckt, es sollten euch
bekannt vorkommen.
Nämlich aus welcher Datenstruktur?
Nämlich aus den Priority Queues.
Die haben ja genau solche Operationen wie dieses Delete Min, was ja im
Prinzip beides macht.
Das entfernt mir dieses Element und ich kriege dieses Minimum in
logarithmischer Zeit und ich kann es entfernen aus der Datenstruktur.
Das heißt also, was Heapsort eigentlich ist, ist ein Selection Sort
mit einer besseren Datenstruktur.
Der normale Selection Sort hat als Datenstruktur ein unsortiertes
Array.
Das ist jetzt nicht besonderlich ausgefuchst, dementsprechend brauchen
wir auch diese Zeit, hier linear um das kleinste Element zu finden.
Was der Heapsort jetzt macht, er nimmt eben diesen Heap als
Datenstruktur und kann damit statt in quadratischer Zeit in nlogn-Zeit
laufen.
Und das Ganze wollen wir uns jetzt an einem Beispiel mal anschauen.
Wir haben hier dieses Array H, da stehen die Elemente drin.
Unter anderem haben wir jetzt auch hier zwei Siebener, bei denen wir
mal untersuchen wollen, ist Heapsort stabil oder ist es nicht stabil.
Und was wir als erstes machen müssen, naja, hier stehen die Elemente
einfach irgendwie drin und es ist noch kein Heap.
Die Heap-Bedingung ist da absolut noch gar nicht erfüllt.
Das heißt also, bevor wir anfangen, da irgendwie zu sortieren, bauen
wir den Heap mit der Bild-Heap-Prozedur, wie es auch in der Vorlesung
vorgestellt wurde, auf.
Das heißt, wir fangen also auf dieser mittleren, auf dieser zweiten
Ebene an und erst mal intuitiv schauen wir jetzt, naja, welches von
den beiden Kindern ist das Größere?
Das ist hier die Neun.
Und dann schaue ich, ist das größere Element größer als mein
aktuelles?
Wenn ja, muss ich es vertauschen.
Wir wollen ja einen Max-Heap aufbauen.
Das heißt, wir wollen das größte Element ganz nach oben bekommen.
Jetzt gehen wir einen Schritt weiter, ein Element weiter.
Wir schauen hier die Vier, die Kinder, die Elemente, die darunter
sind.
Die Sieben ist das Größere von den beiden und ist auch größer als die
Vier.
Also muss ich die auch nach oben ziehen.
Jetzt machen wir noch einen Schritt weiter.
Wir schauen von der Wurzel aus die Kinder an.
Die Neun ist das größere Kind, muss also nach oben gezogen werden.
Und da jetzt haben wir die Zwei nach unten gedrückt.
Jetzt müssen wir auch für die Zwei wieder die Heap-Bedingungen
überprüfen.
Das heißt, auch für die Zwei muss ich jetzt nochmal die Kinder
anschauen und sehe, die ist die Sieben größer, also muss ich die nach
oben ziehen.
Und jetzt in dem Schritt habe ich also meinen Heap aufgebaut.
Jetzt gilt die Heap-Bedingung für alle Elemente im Array.
Und was wir jetzt machen ist, wir wollen damit jetzt sortieren.
Dazu nehmen wir hier diese Heapsort-Variante und die funktioniert
jetzt in place.
Was wir machen ist ein bisschen unsauber.
Wir verringern, während wir diesen Heap benutzen, die Größe des Heaps.
Wir tun es, als würde der sukzessive schrumpfen.
Und wir werden aber sehen, dass das dann funktioniert.
Was wir jetzt also tun, ist, wir ziehen das erste Element, das größte
Element jetzt aus unserem Heap raus.
Und was wir ja bei einem Delete-Max oder so noch machen müssen ist,
man zieht ja das kleinste Element ganz hinten nach vorne.
Und was wir jetzt tun ist, wir verringern die Größe unseres Heaps.
Wir sagen, das letzte Element, was wir jetzt nach hinten geschrieben
haben, das betrachtet man nicht mehr, das gehört nicht mehr zu unserem
Heap dazu.
Und was wir dann machen müssen, für das nächste Element, jetzt müssen
wir die Heap-Bedingungen wieder sicherstellen.
Das heißt, wir rufen jetzt hier Sift Down auf.
Und was jetzt, also vorhin haben wir es ja beim Aufbau, haben wir uns
intuitiv angeguckt, wie funktioniert es im Rechner, im Code läuft es
natürlich anders ab.
Wir schauen uns also, kriegen unser Element 1, wollen wir nach unten
siften.
Das heißt, wir schauen uns die Kinder an, sofern das größere Kind zum
Beispiel existiert.
Und hier dieses K ist gleich K plus 1 brauchen wir nur deswegen, falls
denn das zweite Kind tatsächlich größer ist.
In dem Fall müssen wir dann, wer piepst?
Müssen wir dann eben das Größere der beiden Kinder angucken.
Und dann vergleichen wir eben das Größere der beiden Kinder mit
unserem eigentlichen Element und führen den Swap aus und machen das
Ganze weiter.
Das heißt also, für die 2 müssen wir jetzt in der nächsten Ebene
schauen, was ist das größere Element, naja, sind beide gleich.
Also schiebe ich das eine nach oben, schaue hier nochmal, muss ich
wieder weiter nach unten siften?
Nein, das Element ist kleiner, die 2 ist kleiner als die 1, also bin
ich in dem Schritt hier fertig.
Das heißt, meine nächste Operation ist wieder, ich ziehe die 7 raus
und schreibe sie quasi an diesen gerade freigewordenen Platz, den ich
dann nicht mehr brauchen würde.
Und so geht das Ganze dann Schritt für Schritt durch.
Ich ziehe mal das aktuell größte Element raus, sifte das Ganze wieder
nach unten, um die Heatbedingungen wieder zu erfüllen und so kann ich
also sukzessive mein Array aufsteigen, sortieren, so wie ich das
eigentlich gerne hätte.
Und wenn ich jetzt hier schaue, in diesem Array haben sich die 7er
jetzt hier vertauscht.
Das heißt, Heapsort ist nicht stabil.
Jetzt haben wir das hier in diesem Beispiel abstrakt gesehen, das
wollen wir uns natürlich auch nochmal in Sound of Sorting angucken.
Und zwar, wo ist er denn?
Da ist er.
Und wir haben wieder unsere Arraygröße von 100 Elementen.
Und machen das mal ein bisschen langsamer hier.
Das ging jetzt aber zu schnell.
Und was der jetzt als erstes macht, ist auch diesen Heap aufbauen.
Das ist hier schon ein Stückchen gelaufen, aber ich fange nochmal neu
an.
Ist zu schnell.
Und was er hier bunt darstellt, sind also die Ebenen in unserem Heap,
für die die Heap-Bedingung schon gilt.
Und diese weißen Elemente sind die, für die ich die Heap-Bedingung
noch herstellen muss.
Das heißt also, die ersten Schritte, die hier ablaufen, sind er baut
diesen Heap tatsächlich auf.
Wollen wir das durchlaufen lassen?
Hoffentlich starte ich es jetzt rechtzeitig.
So, jetzt brauchen wir noch ein paar Schritte.
Und er nimmt jetzt hier immer, aktuell ist es dieses rot markierte
Element.
Und jetzt schauen wir wieder die Kinder an.
Welches davon ist größer und vertauschen das Ganze.
Sodass dann am Ende tatsächlich unser größtes Element auch hinten
steht.
Das dauert jetzt ein bisschen lang.
So, jetzt haben wir es gleich gemacht.
Jetzt siftet er das letzte Element runter.
Und dann haben wir es irgendwann gepackt.
Jetzt sehe ich auch, dass er hier mittlerweile schon im Sortieren ist.
Das größte Element ist hier schon rausgezogen.
Und gerade das zweitgrößte an die letzte Stelle geschrieben.
Und jetzt passiert diese Sift-Down-Operation.
Das Element, was ich von hinten nach vorne geschoben habe, geht wieder
runter.
Und wird hier sukzessive nach unten geschrieben.
Und jetzt ist natürlich die spannende Frage, die wir uns schon bei den
anderen Sortieralgorithmen angeschaut haben.
Wie viele Vergleiche brauche ich?
In der Vorlesung haben wir gesehen, es ist in Theta von n log n.
Aber die Frage ist ja, wie viel n log n?
Was ist denn die Konstante genau?
Wenn wir das jetzt hier mal laufen lassen.
Ich habe jetzt 100 Elemente.
Was ist n log n von 100?
Log n von 100, hat der Timo jetzt ja schon ein paar Mal gesagt, ist
irgendwie 6,6 irgendwas.
Das heißt also, wir haben zu erwarten, für irgendwie genau einmal n
log n, so 660 Vergleiche oder so irgendwas.
Jetzt lassen wir es mal durchlaufen.
Wenn wir schon sehen, wir sind jetzt schon...
Nein, noch nicht.
Aber jetzt hier, wir sind irgendwie bei 1026 Vergleiche.
Wir brauchen irgendwie also mehr als n log n.
Wir haben gesehen zum Beispiel beim Mergesort, den wir hier laufen
lassen, der hatte irgendwie nur genau n log n Vergleiche.
Wenn wir den hier durchlaufen lassen, dann sind wir sogar drunter,
unter diesen 600.
Jetzt ist die Frage, wo kommt dieser Faktor 2 her an Vergleichen?
Und das Ganze lässt sich relativ einfach erklären, wenn wir uns hier
diese Prozedur SIFTDOWN nochmal anschauen.
Wo werden denn Vergleiche gemacht?
Zum einen muss ich jedes Mal vergleichen, was ist denn mein kleineres
bzw.
größeres Kind?
Und wenn ich das kleinere oder größere Kind gefunden habe, dann muss
ich nochmal den Vergleich machen mit meinem eigentlichen Element.
Und genau daher kommt also bei Heapsort die Konstante 2.
Wir brauchen ungefähr zwei n log n Vergleiche.
Und das war es auch schon von mir.
Und der Julian macht weiter mit adressierbaren Binary Heaps.
Ja, das ist im Wesentlichen eine Wiederholung von der Vorlesung.
Aber vielleicht eine kurze Motivation noch dazu.
Was wir uns überlegt haben als Motivation dazu.
Stellt euch mal vor, ihr lernt für diese Prüfung demnächst für
Algorithmen 1.
Und dann habt ihr ganz viele Prüfungsaufgaben.
Und was ihr machen wollt, ist, ihr wollt diese Prüfungsaufgaben jetzt
in der Schwierigkeit einfach mal durchrechnen.
Wobei es aber so ist, dass ihr von irgendwem von eurer besten Freundin
nach und nach noch neue Aufgaben dazubekommt.
Und die müssen nicht einsortiert werden.
Und das ist eigentlich das Beispiel für eben eine Priority Queue.
Wie macht man das?
Man sortiert die halt nach Schwierigkeitsgrad und fügt die in so einen
Heap Priority Queue ein.
Und dann bearbeitet man diese Aufgaben.
Bearbeiten sie quasi delete min.
Und wenn eine neue dazu kommt, dann fügt man eine neue ein.
Also wenn das Ganze statisch wäre, es kämen keine neuen dazu, könnte
man einfach sortieren und durchgehen.
Aber dadurch, dass halt immer was Neues dazukommt, ist halt so ein
Priority Queue eine ziemlich gute Sache.
Jetzt erweitern wir das Ganze nochmal.
Und zwar ist es so, jetzt könnt ihr euch überlegen, wenn ihr eine
Aufgabe berechnet habt, dann werden alle anderen Aufgaben dieses Typs
einfacher für euch.
Das heißt, ihr müsst jetzt Aufgaben anpassen können.
Ihr müsst die Schwierigkeit verringern können.
Und zusätzlich könnte es auch sein, dass eure Freundin irgendwo gehört
hat, die Übungsleiter haben behauptet, die und die Aufgaben kommen
nicht dran.
Dann müsst ihr die entfernen aus dem Heap.
Und das ist mit dem normalen Heap ja eigentlich nicht möglich.
Man kann halt nicht auf bestimmte Elemente im Heap zugreifen, sondern
nur auf das Kleinste, auf das Delete Min.
Und aus dem Grund braucht man jetzt halt adressierbare Priority
Queues.
Mit denen es halt möglich ist, zwei zusätzliche Operationen zu
definieren, nämlich das Decrease Key, mit dem man die Schwierigkeit
verringern kann und eben das Remove, mit dem man manche Sachen löschen
kann.
Das Beispiel hört sich jetzt gerade ziemlich weit hergeholt an, aber
was dem eigentlich zugrunde liegt, ist ein sogenanntes Scheduling
Problem.
Und das werdet ihr bestimmt noch im späteren Studium hören.
Das wird auch häufig mit Priority Queues gelöst.
Und ihr werdet auch in dieser Vorlesung noch zwei Anwendungen von
adressierbaren Prioritätslisten mitbekommen.
Also bei den Graphenalgorithmen wird das noch kommen.
Deswegen behandeln wir das auch hier.
Wie macht man jetzt so eine adressierbare Priority Queue?
Also man macht das, indem man zusätzlich zu dem Heap noch ein weiteres
Array speichert, in dem Handles zu Elementen im Heap sind.
Und wenn man jetzt ein Element mit einem bestimmten Index verringern
möchte, kann man in diesem Proxy Array sich das Handle holen und dann
Decrease Key aufrufen.
Jetzt haben wir das Problem, dieses Proxy Array darf nicht statisch
sein.
Denn der Heap ist in Bewegung.
Im Heap werden ja immer Sachen vertauscht, bei dem Sift Up oder Sift
Down, werden ja Elemente vertauscht.
Und dazu müssen eben die Handles auch vertauscht werden.
Und um zu wissen, welche Handles vertauscht werden müssen, müssen die
Elemente im Heap eben auch noch eine Rückreferenz auf dieses Proxy
Array haben.
Das hört sich jetzt gerade ein bisschen viel an, aber ich mache
einfach ein Beispiel dazu.
Also hier haben wir einen Heap, wie vorher, und hier ist die abstrakte
Darstellung, und hier ist die Darstellung, wie man das implementieren
würde.
Und wir setzen hier einfach noch ein Array drunter, wo die Handles
drin stehen.
Und ihr seht, diese Pfeile gehen in beide Richtungen, und die müssen
auch in beide Richtungen gehen.
Beispielshaft habe ich jetzt mal dieses Decrease Key, wie man das
implementieren würde, hier mal hingemalt.
Genau, Decrease Key von einem Handle, man kriegt einen Handle und man
kriegt einen neuen Key.
Der neue Key muss natürlich kleiner sein, sonst decreased man nicht,
und deswegen ist es ganz sinnlos.
Das ist eigentlich ziemlich trivial, man setzt den Key neu, dadurch
wird er kleiner und ist eventuell an der falschen Stelle, und muss
deswegen wieder hochgesiftet werden.
Also wir haben jetzt einen Min Heap hier wieder, im Gegensatz zu dem
ehemaligen Max Heap, jetzt haben wir einen Min Heap wieder, das heißt
das kleine Element ist oben.
Wichtig ist aber, dass man dieses Sift Up jetzt noch anpasst an
unseren adressierbaren Binary Heap.
Und zwar der Art, dass diese Invariante hier immer erfüllt ist.
Wenn man das klug implementiert, muss man eigentlich nur diese Swap
Methode, die hier irgendwie drin versteckt ist, ändern.
Sodass diese Pfeile immer in beide Richtungen gleich sind.
Also ich gehe auf den Element i in dem Proxy Array, finde daraus einen
Handle auf dieses Element hier, und hier muss wieder dieser
Rückpointer, also Proxy ist der Rückpointer, wieder auf das Element
zeigen.
Jetzt führen wir diese Operation einfach aus.
Zum Beispiel, ich will jetzt dieses Element mit der ID 7 verringern
auf 6.
Also gucken wir erstmal hier in unserem Proxy Array auf die 7.
Sehen, dass wir auch hier auf die 7 zeigen in unserem Heap.
Das Element 16.
Als erstes verringern wir einfach die 16 auf die 6.
Jetzt ist es zu klein geworden.
Und machen Sift Up.
Sift Up tauscht nach oben, bis es wieder stimmt, bis die Heap
-Eigenschaft wieder erfüllt ist.
Das heißt, wir müssen mit dem vertauschen, weil die 11 nämlich größer
ist, müssen wir die 6 mit der 11 vertauschen.
Und in dem Moment, wo wir das vertauschen, müssen wir eben auch die
Pointer umtauschen.
Und das ist eigentlich schon alles.
Also jetzt haben wir die 6 und die 11 vertauscht und haben in dem
gleichen Augenblick auch schon die beiden Pointer vertauscht.
Das ist, was ich eigentlich sagen wollte zu adressierbaren Binary
Heaps.
Wie Remove funktioniert, könnt ihr euch auch überlegen, ist eigentlich
ganz ziemlich einfach.
Und es wird dazu auch eine Aufgabe auf dem Blatt geben.
Das war's von mir.
Dankeschön.