Video 9-5: Operationen in Binären Heaps

0:03 Wir hatten uns also jetzt diese Hiebs angeschaut, die so ein bisschen sortiert sind und auch irgendwas mit Bäumen zu tun haben, aber das war alles noch so ein bisschen mysteriös, wie man da draus jetzt eine Datenstruktur machen soll. Insbesondere äh muss ich in so einer Datenstruktur ja Schlüssel einfügen können und löschen können und das ist äh ins besondere das Maximum löschen können. Ähm bevor wir dazu kommen, den Code dazu im Detail anzuschauen, will ich Ihnen das in dieser Animation hier so ein bisschen äh erstmal am Beispiel zeigen. Also, erstens, wenn ich ein neues Element einfügen möchte, da brauche ich kann ich irgendeinen Default Wert nehmen? Ja, geht. Okay. Wenn ich einen neuen Wert einfügen möchte in so einen Hieb, nachdem der so eine strenge Struktur von der Form haben muss, gibt es nur eine Position, wo ein neuer Wert überhaupt hin darf, nämlich genau hier an das nächste freie Stelle Stückchen auf dem untersten Level.

1:05 sprich in dem Fall als neues Kind von dieser 589. Da kommt also ein neues Element immer erstmal hin, denn nirgends anderes darf es hin. Ich versuche ihn klar zu machen, dass die HEBS durch das wie sie definiert sind, die Invarianten der der Form und so weiter eigentlich die Operation komplett vorgeben. Wir haben gar keine Wahl. Jetzt habe ich das Element hier eingefügt. Damit ist die die Form von dem Baum so wie sie sein soll. Aber die zweite Eigenschaft, diese Hiebordnung ist eventuell nicht so, wie sie sein soll, denn hier sehen Sie, der neue Knoten ist größer als sein Elternknoten. Das ist aber verboten. Ah, was könnten wir machen? Na ja, ist ja doof, dass die falsch rum sind. Wie wär es, wir vertauschen die einfach. Das mache ich als nächstes. Äh, da geblieben. Aha.

2:08 Was hat er jetzt getan? Wir mal so. Also, ich mach's ein bisschen kleiner. Da der Wert hier zu groß ist, tauschen wir es mit dem Elternknoten. Und dann ist die Kante hier jetzt in Ordnung. Was ist mit dem anderen Geschwister von diesem Knoten? Die war ja vorher in Ordnung. Vielleicht habe ich die jetzt kaputt gemacht. Nee, kann ich nicht kaputt gemacht haben, denn den Wert, den ich hier hochgepackt habe, der ist ja noch größer als der alte. Die Kante hier ist also noch glücklicher als vorher, wenn das überhaupt geht. Aber ich habe eventuell hier ein neues Problem geschaffen, denn die Kante zu dem Elternknoten vorher, hier war ja ein kleinerer Wert, das heißt, der könnte jetzt verletzt sein. Und hier ist es auch so, die 742 ist größer als die 616. Das heißt, ich muss das noch mal machen und sie sehen schon, wo das hinläuft. Eventuell muss ich bis ganz hoch zur Wurzel tauschen. In diesem Fall kann ich hier aufhören, weil das Element jetzt kleiner ist als das Element drüber.

3:12 Der wichtige Punkt ist, wenn ich so ein neues Element einfüge, wir können gleich noch ein Beispiel machen. Das einzige, was ich dabei potenziell kaputt spiele, ist ganz lokal. Anderswo im Baum ändere ich nichts. Da gehen diese Sortierungen entlang der Kanten nicht kaputt. Und wenn ich einfüge, dann kann ich immer nur was kaputt machen zu meinem Elternknoten, niemals zu meinem Geschwisterknoten, denn der war schon vorher glücklich und wird dann nur noch glücklicher. Machen wir noch ein Beispiel. ähm zufällige Zahl hier gewählt, die ist jetzt relativ klein. Da werde ich hier einmal noch tauschen müssen. Ja, aber da bin ich jetzt schon zu Ende. Fertig. Also einfügen ist echt leicht. Okay, ich muss immer einfach nur das nächste freie Element hier ähm mit dem mit dem neuen Knoten belegen und dann so lange nach oben tauschen, bis das Element seinen Einfügepunkt gefunden hat. Achten Sie beim nächsten Mal vielleicht auch hier oben noch auf dem Array. Das ist jetzt hier so gemalt, als würde ich das Array vergrößern. In Wirklichkeit habe ich natürlich da wieder die üblichen Probleme. Ich habe eine Maximalkapazität, die ich irgendwann anlegen muss und bei Bedarf verdoppeln sowas in der Art. Für viele Anwendungen ist die Maximalkapazität vorher tatsächlich bekannt, dann ist das gar kein Thema. Also einfügen heißt ein neues Element da hinten anhängen, da das ist wieder zentriert, aber es ist tatsächlich einfach nur ein neue neuer Wert hier hinten angehängt worden. Und das Vertauschen passiert natürlich auch genau entlang vom Array. Von 24 ist die Vertauschung mit 12, also hier diese lange Distanz. Ich muss natürlich ein paar mal vertauschen. Der Wert hier ist ja zu groß. Jetzt ist es nach oben getauscht.

4:57 Und äh dann sehen Sie hier, die Kante ist glücklich. Das heißt, wir sind schon wieder fertig. Was man hier in dem Array wahrscheinlich ganz schwierig sehen würde, ist welche Vertauschung muss ich machen? Dafür muss ich immer rechnen mit dem Index halbieren. Aber im Baum ist es einfach. Das war insert. Ähm, den ersten Teil schon einmal abhandeln. äh die Operation nach oben tauschen, die ist hier Swim genannt. Stellen sich vor, das Element boppelt so nach oben, bis es dann seinen Einfügeposition eben gefunden hat. Und ich kann das in Java auf diesem Array ganz effizient machen, auch wenn es bisschen unintuitiv ist. Ich vertausche einfach immer mit dem Index halbiert. Sie wissen, in Java rundtet das von alleine ab. Das Flor brauchen wir nicht. Und ich mache das so lange, bis mein Wert jetzt äh nicht mehr kleiner ist als das älter äh bis mein Wert äh bis der Elternwert nicht mehr kleiner ist.

6:18 Und damit kann man Insert wie folgt realisieren. An die nächste Position hinten schreibe ich das Element und ich rufe einmal Swim auf. absurd kompakter Code, aber ich denke, wenn man sich das nur auf dem Array anguckt, kapiert man nicht, was äh was abgeht. Man möchte schon die ähm Illustration an dem Baum sich als Vorbild nehmen.

6:42 Okay, das heißt, wir können einfügen, wie sieht's aus mit Maximum entfernt? Das ist die andere große Operation, die wir unterstützen wollen. Auch hier wieder, wo das Maximum ist, eindeutig bestimmt, muss in der Wurzel sein. Wenn ich es also entfernen möchte, dann will ich die Wurzel entfernen. Das kann ich aber nicht. Das ist ja nicht erlaubt nach der Form in Variante. Das Ding wird hinterher ein Wert kleiner werden. Der einzige die einzige Stelle, wo ich einen Wert entfernen kann, ist wieder hier unten das letzte Element im untersten Level. Also, ich habe einen Wert, den ich entfernen will und eine einzige Stelle, wo ich einen Wert wegnehmen darf. lassen Sie uns halt die beide tauschen und den oberen Wert hier zurückgeben, dann können wir den Wert hier unten entfernen. Okay, also für Maximum löschen ähm wurde hier jetzt direkt der das Maximum entfernt. Äh was ein bisschen es springt ein bisschen rum hier mit dem, aber eigentlich ist äh ja im Ray direkt den den Wert entfernt.

7:38 Eigentlich ist hier nur diese Kante verschwunden, weil dieser Knoten jetzt nicht mehr wirklich existiert. Und die Wurzel ist leer. Wir schreiben den Wert hier in die Wurzel und fertig. Jetzt ist der Hieb wieder von der Form so wie er sein soll. Vollständiger binärer Baum bis vielleicht auf das letzte Level, wo alles so weit links ist, wie es geht. Aber es ist noch die zweite Eigenschaft kaputt, denn jetzt habe ich hier in aller Regel was äh in die Wurzel gesetzt, was vorher ganz unten auf dem Level der Blätter war. Höchstwahrscheinlich ist das hier eher ein relativ kleiner Wert. Könnte, wir wissen nicht viel über den Wert, außer dass er äh in dieser Reihe von Spielen mit diesen auf dem Fah, na ja, Quatsch, mit diesen hier. Also, wir wissen, die 72 ist definitiv kleiner als diese drei Werte. Also das neue Maximum ist es auf jeden Fall nicht. Aber gut, was machen wir? Wir müssen wieder irgendwie diese Hiebeigenschaft herstellen. Das heißt, wir vertauschen den irgendwie nach unten. Dummerweise haben wir jetzt zwei Richtungen, wo man hin vertauschen kann. Welche nehmen wir denn? Aber auch das ist wieder eindeutig bestimmt. Ich muss ja hinterher die Eigenschaft auf beiden Kanten wiederherstellen. Ich habe zwei Optionen. Ich könnte das hier in die Wurzel tauschen oder ich könnte die zwei Werte tauschen.

8:58 In beiden Fällen habe ich hinterher eine Kante zwischen den aktuellen Geschwistern. Das heißt, ich muss das größere der Geschwister in die Wurzel packen. Das heißt, ich brauche hier zwei Vergleiche. Der erste ist zwischen den beiden Geschwister äh Knoten. Da finde ich raus, dass der hier größer ist. Und dann mache ich die Vergleich, ob der hier denn auch kleiner ist als das hier. In dem Fall ist beides der Fall. Das heißt, die beiden werde ich vertauschen müssen.

9:32 Das heißt, ich vertausche mit dem hier. Jetzt ist diese Kante auf jeden Fall glücklich. Die habe ich gerade verglichen. Den ganzen linken Teilbaum habe ich gar nicht angefasst. Der ist immer noch glücklich. Der rechte Teilbaum. Na ja, da habe ich jetzt wieder was in der Wurzel ersetzt durch einen kleineren Wert. Das ist potenziell schwierig, aber ich bin in rekursiv genau der gleichen Situation wie eben. Ja, ich habe wieder eine Wurzel neuen Wert. Das heißt, ich vergleiche die beiden Kinder. Der hier ist größer. Das heißt, die beiden muss ich tauschen, weil die 72 in der Tat kleiner ist als die 927.

10:05 Dann habe ich die gleiche Situation noch mal wieder. Der rechte Teilbaum kann nicht kaputt gehen, weil ich den gar nicht verändert habe und die einzige Kante, die sich geändert hat, habe ich gerade explizit verglichen. Aber die 72 hier ist immer noch nicht glücklich. Das heißt, ich mache das noch mal einen Schritt. Größeres Kind nach oben, 72 nach unten und jetzt sind wir fertig. Wenn ich das Blattlevel erreicht habe, dann kann die 72 nicht mehr irgendwie zu klein sein. Okay, noch eine Runde. Äh wir machen das ganze Spiel noch mal auch hier wieder. Einzige Option, ich ich lösche die Wurzel. Einzige Option, ein Element zu entfernen, ist dieses hier. Das heißt, der Wert kommt in die Wurzel und dann lasse ich wieder versickern. Größeres der beiden Kinder ist hier das rechte. Mit dem tausche ich, weil die 419 kleiner ist. Und rekursiv so weiter wieder. Ich bin kleiner als das größere Kind. Tauschen. Happy. Ich bin größer als die beiden Kinder. Das heißt, ich darf bleiben, wo ich bin. Kein weiterer Vertausch.

11:13 So funktioniert das Delete Maximum. Und auch hier ähm möchte ich ihn wieder einfach ähm unter die unter die Nase reiben, wie wenig Wahlmöglichkeiten wir eigentlich haben. Dadurch, dass die Form von diesem Hieb so fest eingeschränkt ist, bleibt uns gar nicht viel anderes übrig, als genau diese Schritte zu machen.

11:40 Die Basisoperation, die wir jetzt hier verwendet haben, die heißt hier Sync oder äh DMTI. Äh das Gegenteil von Beförderung, ne? Äh äh ich habe einen Knoten, der jetzt nach unten versickert. Ich vergleiche immer meine zwei Geschwister, die zwei Kinder. Das kleinere davon merke ich mir in J. Das ist clever gelöst, indem ich den Index auf das eine setze und erhöhe, falls das andere kleiner, größer war. Und solange ähm mein aktueller Knoten ähm nicht größer ist als der hier, vertausche ich und gehe zu dementsprechenden Kit. Ja, also was ich Ihnen hatte zeigen wollen, ist der Code hier ähnlich kompakt wie eben. Es gibt diesen Index J, der das Kind äh speichert, das den größeren Schlüssel hat, indem ich den entsprechend hier ähm erhöhe, wenn nötig. und ich mache den Vertausch so lange, bis die Hiebeigenschaft wiederhergestellt ist. Damit kann ich das Maximum löschen. Hatten wir eben ja ein Beispiel gesehen äh im Code auch sehr kompakt wieder.

12:47 Ähm ich finde das Maximum an Position 1, nicht 0. Sehen sich null ist leer. Ich vertausche den Wert an dem aktuell Position n in die Wurzel und lass den versickern.

13:04 Damit kann ich das Maximum löschen. Ähm, wir hatten jetzt gar nicht so arg über die Operationskosten gesprochen, aber in beiden Fällen habe ich eine Operation Swim und Sync, die einen Pfad von der Wurzel zu einem Blatt äh abschreitet, entweder von unten nach oben oder von oben nach unten. Aber mehr tut sie nicht. Das heißt, die Kosten sind in jedem Fall gedeckelt durch die Höhe von dem Baum. Und den hatten wir ja vorhin analysiert oder ich hatte das Ergebnis zitiert, dass Sie schon analysiert hatten. Der hat Logarithmus 2 zur Basis 2 von n Höhe. Das heißt, in beiden Fällen sind die Operationen effizient.

13:40 Äh hier ist noch mal die komplette Implementierung. Das ist aber im Wesentlichen der Code, den sie eben gesehen haben, zusammengepackt äh mit diesen Hilfsoperationen. Äh da passiert nicht viel äh spannendes mehr. Das heißt, für diese ähm Priority Queue Operation haben wir jetzt eine Lösung gefunden, die für beide Operationen, für die beiden Schlüsseloperationen, also einfügen und löschen, logarithmisch viel ähm Zeit nur braucht. Das Get habe ich nicht wirklich. Ich kann nicht wirklich für beliebige Schlüssel den Wert auslesen, den ich dazu gespeichert habe. Das können Priority Cues einfach nicht. Deswegen war das auch so ein bisschen einfacher als die ursprüngliche Aufgabe, aber zumindest haben wir die einfache Aufgabe gelöst. Und die Datenstruktur war ziemlich einfach, wenn man mal diesen göttlichen Einsichtsfunken ähm als gegeben annimmt, dass man eben genau diese Struktur von dem Hieb und genau diese Sortierung zwischen den Eltern und Kindknoten als gegeben annimmt.

14:53 noch so ein paar ähm Randbemerkungen ähm in der Implementierung, die wir dann die man irgendwie anderen Programmieren an die Hand geben will, wie man noch so ein paar Sachen einfügen, ähm die dafür sorgen, dass die Operationen nur aufgerufen werden, wenn sie Sinn ergeben. Abstrakt gesprochen.

15:09 Äh wenn man ein Doubling Array verwendet, kann man beliebig große Hiebs haben. Dann hat man aber diese amortisierten Kosten. Sie erinnern sich an die Münzen, die man zahlen muss für das Verdoppeln. Man kann natürlich eine minorientierte Variante machen, entweder indem man die Schlüsselreihenfolge umdreht, äh oder indem man den Code entsprechend anpasst. Das ist symmetrisch. Äh man kann auch noch ein paar andere Operationen unterstützen auf den HEBS. Die sind dann für weiterführende Anwendung eventuell spannend, aber würde ich jetzt hier nicht im Detail besprechen. Also man kann mit den gleichen Operationen ein beliebiges Element entfernen dazu vielleicht oder auch die Priorität von dem Element ändern. Dazu vielleicht einfach noch mal kurz auf das Bild. Wenn Sie sich irgendeinen Knoten nehmen und jetzt den entfernen möchten, sie haben wieder nur eine Möglichkeit. Sie tauschen dessen Wert mit dem letzten und lassen den entweder aufsteigen oder versickern. Das kommt jetzt drauf an, wie der Wert hier sich verhält zu den Eltern und Kindern.

16:06 Da kann es jetzt beide Fälle geben. Das ist das einzige, was Neues. Ebenso, wenn Sie beschließen, ah, dieses Element, das hat jetzt nicht mehr Priorität 742, sondern einen anderen Wert. Dann schreiben sie den neuen Wert dahin und prüfen auch wieder, muss ich aufsteigen oder versickern. Es passiert immer nur eins von beidem. Welches davon hängt davon ab, wie sie den Wert geändert haben? Wenn Sie ihn vergrößern, kannst du nur aufsteigen. Wenn Sie ihn verkleinern, kannst nur absinken. Beide Operationen sind genauso wie vorher. den die merken gar nicht, dass sie in der Mitte anfangen, nicht ganz unten oder ganz oben. Und äh die Operationskosten sind natürlich auch noch gedeckelt durch die Höhe vom Baum, denn sie laufen wieder nur ein Fahrt von Wurzel zu einem Blatt ab, höchstens.

16:56 Ja, subtile Annahme ist, dass der ähm dass die Schlüssel nicht geändert werden, ohne dass wir davon informiert werden. Das ist so wie es gibt in der Java Library eine Implementierung von genau diesen Priority Cues, die das zwar in der Dokumentation beschreibt, aber es ist sehr sehr leicht ähm darauf reinzufallen. Also behalten Sie es im Hinterkopf. Diese ganzen Datenstrukturen funktionieren nur unter der Annahme, dass sie nicht einfach den Wert von dem Schlüssel verändern, ohne der Datenstruktur Bescheid zu sagen. Und ich denke, von dem Bild ist wieder klar, wenn jemand den Wert von einer dieser Zahlen in dem Hieb einfach verändert, dann ist halt diese Invariante nicht mehr erfüllt, dann geht alles mögliche schief.

17:42 Kurzer Nachtrag noch aus dem Sortierkapitel. Wir hatten damals gesagt, ah, da gibt's noch ein drittes Verfahren neben Quicksort und Merch Sort, mit dem man auch recht schnell sortieren kann, nämlich HEBSort. Und jetzt wissen Sie auch, was das mit dem Hieb da gemeint ist. Das einzige, also konzeptionell können Sie einfach ähm vergessen Sie kurz die Folie. Sie können konzeptionell alle Daten, die Sie sortieren wollen, in den Hieb einfügen und nacheinander das Maximum rauspflücken, dann haben sie die Eingabe sortiert. Man kann das aber hier ein bisschen cleverer machen, weil der Hieb ja auch in dem Array lebt und weil wir einen Maxheib haben, der immer im Array von hinten schrumpft. Das heißt, man kann den das Array, das man sortiert, selbst als Hieb verwenden, indem man die Elemente passend umsortiert und dann sukzessive das Maximum entfernen und an das letzte die letzte Position tauschen. Dadurch schrumpft der Hieb automatisch von hinten ein Stück. und wir können quasi die Elemente belassen, wo sie sind. Das heißt, das ist ein Inplay Sortierverfahren, was keinen Zusatzspeicher benötigt.

18:51 Äh, es gibt eine effiziente Variante, den Hieb aufzubauen. Die ist schneller als n mal einfügen. Ähm, können Sie sich in Ruhe angucken. Äh, würde ich hier sozusagen ausklammern, müssen sie von mir aus nicht wissen. Und das Sortieren selbst ist dann ganz ganz einfach. Ich habe einfach den das Maximum nach hinten getauscht und mach dann einmal sync für den Delete Max Aufruf. Damit haben wir ein drittes Sortierverfahren, äh das eben auch effizient arbeitet. Die Java Implementierung, wenn man diese Sync Methode von vorhin übernimmt, ist dann auch sehr sehr kompakt.

19:35 Und hier noch mal die aktualisierte Tabelle mit den ganzen Sortierverfahren. Also, fast alles kennen Sie hier schon. Äh, den können Sie ignorieren, den haben wir nicht besprochen, aber Hapsort ist jetzt hier ein neuer Eintrag, der ist in Place und hat diese Worstcease Garantie von fast n log vergleichen. Also ist äh ungefähr in der Kategorie von Merchort und Quicksort, die wir besprochen hatten und hat aber so ein bisschen kombiniert andere äh Eigenschaften. Merchsort hat Zusatzplatz gebraucht, ist nicht in Place. Quicksord ist zwar in place, hat aber diesen schlechten worst case und Hapsort kombiniert so diese ander es ist sozusagen die anderen beiden Dinge kombiniert. Das noch so als Nachtrag und für die Haps selbst äh wenn man die ganzen Operationen der Priority Queue äh so implementiert, wie Sie es gesehen haben, dann können wir effizient Insert Delete Max und change key alles in logarithmischer Zeit. überhaupt ist nur eine Operation teurer und das ist aber die hier, die den Hieb komplett aufbaut. Die wäre sonst n log n. Das heißt, das ist auch okay.