Video 9-4: Binäre Heaps

0:02 Wir hatten gesehen, die elementaren Ideen für Symbolle Tables einfach eine verkettete Liste oder ein Array nehmen, das haut nicht so richtig hin. Deshalb erstmal ein Spezialfall von einem eingeschränkten abstrakten Datentyp. Äh Klammer auf, sie haben den auch schon im Sortierkapitel kurz angeteasert gesehen damals äh hatte ich gesagt, wir machen das später. Und noch ein weiterer Vorg, wir werden dann auf den abstrakten Datentyp im Grafkapitel noch mal kurz zurückkommen, aber ich möchte ihn hier als Spezialfall von Symbolle Tables vorstellen, weil das äh bisschen ein schöner Zwischenschritt ist zu dann den Implementierungen, die wir danach anschauen für alle Symbolle Tables. Also, was worum geht's hier? eine eine Priority Queue oder Prioritätswarteschlange, wenn sie bevorzugen, ähm hat die folgenden Operationen, ähnlich wie Symle Tables kann ich kann ich Schlüssel einfügen. Ähm bisschen die Notation ist ein bisschen anders, wie man das üblicherweise äh für Priority Cues hat. Ich habe einen Wert, den ich zuerst einfüge und dann ist die Priorität ist der Schlüssel oder was wir in den Symle Tables als Schlüssel haben. Ähm, das ist aber jetzt nicht ein allgemeiner Wert, sondern so ein bisschen wie wie schnell möchte ich dieses X hier wiedersehen, denn die Gegenoperation ist das Maximum aus der aus der ganzen Priority Que entfernen. Also, ich kann Elemente einfügen mit einer gewissen Priorität in beliebiger Reihenfolge. Ja, die ist egal. und kann dann aber hoffentlich schnell das Maximum aus allen Elementen, die aktuell in der Priority Cue gespeichert sind, entfernen oder finden und entfernen.

1:40 Finden geht natürlich auch. Ähm, zusätzlich gibt's noch so eine Operation, die aus einer aus einem Array von Werten diese Priority Queue erstellt. Ähm, kann man hier schneller machen als für Ierativ insert. Deswegen ist das eine extra Operation. Äh, für den Moment ignorieren wir Change Key, wo ich also ein Element, das schon gespeichert ist, mit einer neuen Priorität versehe. Ähm, die Kernoperationen für uns sind erstmal Insert und Delete Max. Das ist so ein bisschen eine eingeschränkte Version von der Symbol Table. Die ist schon schon sehr eingeschränkt. Ich kann nicht mal Get aufrufen, aber sie werden sehen, es gibt hier einen ähnlichen ähnlichen Tradeoff ähm wie wir ihn eben gesehen haben. Deswegen dieses Problem zu lösen bringt uns an der Stelle erstmal ein Stück näher an die an die Ideen für allgemeine Symbolle Tables, sozusagen mehr die didaktische Motivation, als dass sie inhaltlich äh das die gleiche Aufgabe hätten in der Anwendung. Äh, wir hatten hier alles als maximum orientiert definiert. Sprich, ich kann das Maximum schnell finden und das Maximum schnell lösen. Was ist mit Minimum?

2:49 Pech gehabt. Minimum geht nicht. Zumindest erstmal laut der dem abstrakten Datentyp dürfen sie nur über das Maximum sich hermachen. Es gibt eine symmetrische Version und je nach je nach Buch oder je nach Quelle wird das mal so rum oder mal so rum definiert. Ich halte mich an die Version, wie es auch im Crick Rainbuch ist mit Maximum ähm wie es zum Sortieren passt. Beides macht Sinn. Es gibt es auch eine minoriented Priority Que, min pq, wo einfach überall wo eben max und größter Stand kleiner steht. Ähm nur damit Sie Bescheid wissen, dass beides äh beide beide Terminologien werden verwendet.

3:33 Vielleicht weniger offensichtlich als bei Symbolle Tables haben auch Priority Cues eine ganze Reihe von Anwendung und eine besonders ähm hübsche, wo ich noch auf eine Gelegenheit warte, ihn vielleicht eine praktische Aufgabe dazu zu basteln, sind Event Driven Simulations. Das ist dieses Bild hier unten. Äh so kollidierende Objekte, die sich in 2D bewegen mit konstanter Geschwindigkeit. Vielleicht haben Sie sich mal gefragt, wie man das effizient implementiert. Die Antwort ist im Wesentlichen mit einer Priority Queue, in der ich die Bewegung all der Objekte analysiere und vorhersage, wann wird's die nächste Kollision geben. Dieses dieses Event füge ich in eine Priority Queue ein mit der Zeit und dann nehme ich in jedem Schritt der Simulation das nächste Event, das also am äh den den kleinsten Zeitstempel hat, da wäre min PQ wahrscheinlich bequemer. äh nehme ich mir aus der Priority Queue raus und berechne, was das für ein Effekt hat. Und das ist im Wesentlichen die Art, wie man solche Simulationen effizient gestaltet, in der sich ganz viele Objekte sonst bewegen. Wenn Sie das anders versuchen, kommt sie sehr schnell zu dem Schluss. Es ist gar nicht so einfach, das schnell zu machen. Davon abgeleitet gibt's ähm diverse andere Anwendungen. Äh wir werden dann auf so Dinge wie Suche in Grafen noch mal zurückkommen. Äh hier noch mal ein extra Punkt.

4:55 Für die vielen anderen Dinge äh belasse ich es mal einfach nur mit der Liste. Da ist die Java Version zu dem abstrakten Datentyp. Wir haben Schlüssel, die vergleichbar sind, ansonsten sind die Operationen, wie Sie sie vermuten würden. Ähm es gibt hier, wie ihn vielleicht auffällt, keine Werte. Also die Variante ist so gebaut, dass er letztlich es nur ein Objekt gibt, Key und das ist sortiert, das ist geordnet, das ist die Priorität in der Schreibweise von vorhin. Und wenn Sie dem zusätzliche äh Daten mitgeben wollen, dann muss dieses Keyobjekt die eben mit direkt speichern.

5:45 Ähm ja, wann es irgendwie gibt, darf die Implementierung irgendein Maximum wählen. Da gibt's keine Konvention für. Also, das haben wir Klassiker gemacht in der Forschung. Wenn man eine Frage findet, die schwierig ist, dann versucht man erstmal eine Antwort auf eine andere Frage zu finden und die Leute davon zu überzeugen, dass das hilfreich ist. Das ein bisschen augenzwinkernd. Ähm, wir werden gleich darauf zurückkommen, inwiefern das hier auch zu zutrifft. Auch hier wieder erstmal, ich habe Ihnen gesagt, das ist der gleiche ähm inherente Tradeoff, den wir hier vorfinden. Wenn man einfach lineare Listen verwendet, entweder unsortiert, dann kann ich zwar schnell einfügen oder der Annahme, ich kümmere mich nicht um Duplikate, aber das Maximum finden, wenn die Liste nicht sortiert ist, na ja, da muss ich alle Elemente einmal anschauen. Wenn ich die Liste sortiert vorhalte, dann kann ich es so anlegen, dass das Maximum ganz vorne steht. Dann komme ich schnell dran. Beinfügen kostet wieder Linearzeit, entweder, weil ich ein Array verwendet habe und dann zwar schnell die Position finden könnte, aber dann muss ich wieder eine ganze Reihe vom Array kopieren oder ich habe eine verkältete Liste und dann kann ich sortiert einfügen, auch nur indem ich durch die Liste durchlaufe. Also genau der gleiche Tradeoff, wie wir es eben hatten.

7:03 Und ähm was die Lösung zu sein scheint hier ist, dass wir irgendwie weder ganz sortiert noch ganz unsortiert brauchen. Können wir das irgendwie hinkriegen? Was was soll das sein? Eine ein bisschen sortierte Liste und die Antwort ist ein Hieb. Äh, es gibt hier tatsächlich für diese Priority cues ähm für das allgemeine werden wir uns ein bisschen mehr anstrengen müssen, allgemeine Symbolle Tables, aber für Priority cues gibt's eine Antwort auf dieses ein bisschen sortiert. Und die formale Definition steht hier. Ähm, ich werde die gleich kurz einmal vorlesen, aber die ist nicht intuitiv. Ich jetzt sage Ihnen gleich, wie Sie daüber nachdenken wollen, aber man sieht in der Darstellung, dass es so ein bisschen sortiert schon ist. Für jeden Index ist der Wert an diesem Index kleiner als der Wert zur Hälfte. Also, wenn ich den Index halbiere, irgendwie ein Stückchen weiter nach vorne springe, ist der Wert dort kleiner als mein Wert. Eine sortierte Liste erfüllt das. Da ist ja immer der Index genauso geordnet wie die Werte. weiter nach links heißt kleiner oder größer hier in dem Fall.

8:16 Ja, wir sortieren absteigend, aber es ist auch nicht sehr arg sortiert, denn äh ich habe diese Eigenschaft nur ich habe im Prinzip nur I äh Vergleiche festgelegt. Gibt ja nur soll nicht I, nur n Werte von nur n Vergleiche festgelegt, werden wir zum Sortieren, wie Sie jetzt auch schon wissen, mit nur n vergleichen nicht auskommen.

8:41 Das ist die Definition, die ist aber ähm, wenn ich Ihnen das jetzt gebe und sage, implementieren Sie mal eine Priority Queue, dann ist er wahrscheinlich erstmal eine Weile Kopfkratzen angesagt. Es gibt eine andere Sichtweise auf genau diese Definition, die sehr viel intuitiver ist, nämlich das Ganze als einen Baum aufzufassen und zwar ein binärer Baum, in dem also jeder Knoten hier ein linkes und ein rechtes Kind hat. Das sei denn, es ist es unten ein Blatt, dann hat er die eventuell nicht. Es gibt so ein einen Ausnahmeknoten, der vielleicht nur ein Kind hat. Ich habe aber nicht einen beliebig strukturierten Baum, sondern eine ganz ganz strenge Form, wie es hier angedeutet ist. Ein vollständiger minärer Baum. Alle Level sind komplett gefüllt. Ich habe nirgends fehlende Kinder, außer in der letzten Ebene, wo ich dann vielleicht keine Knoten mehr habe. Und dann ist auch noch in der letzten Ebene alles so weit nach links geschoben, wie es geht.

9:40 Okay, also für jede Größe n an Knoten gibt's genau eine Form, wie dieser Baum aussehen darf. Ähm hier für was sind das? 7 5 für 12 ist das eben der eine Fes andere N gibt's auch genau eine Form, wie der aussehen darf. Das ist dieser erste Teil. Und der zweite Teil, der ergibt sich daraus, dass wir diese Knoten in dem Baum passend zu den Indizes äh abbilden, sodass der Baum hieb geordnet ist. Sprich, jedes Mal ist das ist der Elternknoten Knoten größer als der Kindknoten.

10:24 Wenn ich das ähm mit den Indizs passend wählen möchte, dann muss ich den Baum in dieser Reihenfolge durchnummerieren. Ich fange der Wurzel an mit ein. Dann gehe ich in das nächste Level und lauf hier 2 3 Level für Level hier durch und fang immer wieder links an. Ja.

10:52 Wenn ich das in diesem Baum mit dieser Reihenfolge mache, Level für Level, links von rechts, 1 2 3 4 5 6 und so weiter, dann sind das Indices in dem Array mit genau der magischen Eigenschaft, dass von jedem Index die Hälfte nehmen und abrunden mich zum Elternknoten bringt. z.B. 5/ halbe ist 2,5 abgerundet ist 2 voila, das ist der Elternknoten. Das gilt hier überall. Das liegt einfach daran, dass die Anzahl Knoten oberhalb von einem Level ist immer eine zweier Potenz -1 und dann kann man den Rest berechnen. Ähm, sie können den Baum dann auch so malen, dass der zu den Positionen im Array passt. Das sieht man dann relativ schnell hier, relativ wenig, deswegen ist das äh begrenzt sinnvoll. Für kleine Beispiele hilft's aber. Okay.

11:46 Äh hier in diesem Baum habe ich die Indices in die Knoten gemalt. Eigentlich stehen da aber die Werte an dieser Position im Array. Und wenn ich das dann tue, dann soll das Hieb geordnet sein. Z.B. Ähm, könnte das so aussehen.

12:11 Da habe ich ein Array mit Zahlen. Das ist der eigentliche Hieb. Und sie sehen z.B. von 4 die Hälfte ist 2. Also der Wert bei 2 ist größer als der Wert bei 4. Das ist auch hier so. Und ich kann die passenden Knoten dazu finden, indem ich die der Länge dem Level nachdurchgehe. 1 2 3 4 Da ist meine vier und hier ist das das Eltern der Elternknoten. Hier in der Animation sind die ähm habe ich gemacht. Also je je röter je roter röter gibt's nicht. Je roter desto größer der Wert. Ähm, wir können mal ein paar mehr Knoten einfügen, dann ist das ganz etwas größer. Jetzt habe ich 20 insgesamt. D sehen Sie gleiches Muster. Ich habe genau eine Form für den Baum, ja, ein vollständiger Gabinärbaum und das letzte Level so weit links, wie es geht. Was ich auch sehen hier dem Beispiel ganz ganz schön, ähm zwischen z.B. zwei Geschwisternknoten gibt's keinerlei konsistente Ordnung, außer dass es jetzt hier zufällig hier haben wir mal so ein Beispiel. Hier ist der link das linke Geschwister größer als das rechte. Hier ist bei den Blättern sind die kleinen immer größer.

13:23 Das ist auch ein Maxhieb. Das heißt, das Maximum ist in der Wurzel. Aber wo das Minimum steht, ist völlig unklar. Das ist irgendeins der Blätter hier unten. In dem Fall das hier, aber das ist gar nicht klar. Also das Maximum in so einem Ding finden ist schwierig. Minimum. Das Minimum in so einem Hieb finden ist nicht klar. Würde man irgendwo die Blätter durchsuchen müssen.

13:54 Okay. Seltsame Definition, nicht? Wah? Und das soll eine gute Datenstruktur werden. Schauen wir mal. Äh hier noch mal ähm aus den anderen Folien für den den Teil hier oben hatten wir abgedeckt, was ich noch erwähnen wollte. Das ist das Lämmer, das sie im Wesentlichen auch schon bewiesen hatten. Ähm die Höhe von so einem vollständigen Binärbaum ist Anzahlknoten, Logarithmus und dann abgerundet, aber um und bei ist es log n logis 2 von n. Das sollten wir im Kopf behalten. Insbesondere ist die Höhe sehr klein im Vergleich zu der Anzahlknoten.

14:36 Äh spaßige Sache, es gibt diese coolen Dumpalmen, die tatsächlich wachsen wie binäre voll wie vollständige binäre Bäume. Ähm wollte ich ihn nicht vorenthalten. Hier auch noch mal äh das Bild von oben gemalt mit Schlüsseln diesmal. Also hier sind in dem Beispiel Buchstaben als Schlüssel. Der alphabetisch größte steht in der Wurzel und hier ist die Abbildung, wie das zu dem Array passt. Da haben Sie genau die Korrespondenz noch mal zwischen äh Baum und Array Darstellung. Ähm, wichtig, hier hat ich so ein bisschen schnell drüber gehuscht, damit Sie es nicht merken. Die Rechnerei wird bequemer, wenn wir davon ausgehen, dass die Wurzel den Index 1 hat, nicht 0. Das heißt, wir haben einfach in unserem Array den Eintrag bei null immer leer gelassen, den benutzen wir nicht. Das macht einfach weniger Ärger bei dem Index berechnen. Sie könnten das natürlich auch immer dann abziehen. Äh die Konvention für die Vorlesung ist, wir fangen dabei eins an. Das heißt, die erste Arrayzelle, die verschenken wir.

15:43 Okay. [schnauben] Das Maximum finden ist ganz ganz einfach, denn das ist immer in der Wurzel. äh wäre das nicht so, gäb es irgendwo eine Verletzung, denn ähm die Wurzel ist zumindest induktiv ein Elternknoten von jedem anderen Knoten. Das heißt also, dass ich das hier an jeed entlang jeder Kante die Eigenschaft habe, dass oben kleiner ist als unten. Andersrum oben größer ist als unten. Diese Minion Max Geschichte macht mich fertig. äh Maximum ist oben. Also an entlang jeder Kante habe ich Maximum oben, Minimum unten. Ja, von diesen zwei bedeutet sofort, dass ich das auch induktiv für alle habe. Wenn das Minimum, wenn das Maximum irgendwo anders stünde, dann wäre an der Stelle die Elternkante verletzt. Das einzige, wo ich keine Verletzung mit einer Elternkante haben kann, ist, wenn ich keine habe und das gilt nur für die Wurzel.