Am 14. September 2017 haben wir eine überarbeitete Fassung unserer Datenschutzrichtlinie veröffentlicht. Wenn Sie video2brain.com weiterhin nutzen, erklären Sie sich mit diesem überarbeiteten Dokument einverstanden. Bitte lesen Sie es deshalb sorgfältig durch.

Grundlagen der Programmierung: Datenstrukturen

Heaps

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Bei Heaps spielen binäre Suchbäume die Hauptrolle. Je nach Art des Heaps erscheint als Wurzelknoten immer der niedrigste oder höchste Wert.

Transkript

Abhängig von der Sprache, mit der Sie arbeiten, sind Sie vielleicht mit dem Begriff Heap vielleicht vertraut. Also einem Gebiet des Speichers, in dem Sie Objekte zuordnen können. Aber das ist jetzt nicht das, was wir meinen. Ein Heap ist auch eine bestimmte Datenstruktur, die wir für unsere eigenen Zwecke nutzen können. Sie werden oft in Sortieralgorithmen verwendet. Vielleicht haben Sie auch schon etwas von HeapSort gehört. Aber sie sind auch eine Möglichkeit, andere abstrakte Datentypen zu verbessern oder innerhalb dieser anderen Datentypen eingesetzt zu werden. Heaps werden normalerweise als binäre Bäume implementiert. Nicht als binäre Suchbäume, sondern als binärer Baum. Das ist einfach nur eine Sammlung von Eltern-Kind-Knoten. Mit einem Maximum von zwei Kindern und einem beliebigen Elternteil. Aber da ist noch etwas anderes. Ein anderes einfaches Gesetz, dem ein Heap folgt. Sie können es hier schon sehen: Es gibt eine Reihenfolge. Es geht immer von oben nach unten und dann von links nach rechts. Oben-unten, links-rechts. So wird diese Baumstruktur immer gleichmäßig aufgefüllt. Wir haben hier nicht das Problem wie bei binären Suchbäumen, dass es in eine Richtung ein besonderes Ungleichgewicht bekommen könnte. Aber es sind nicht wahllos hinzugefügte Dinge in einer zufälligen Reihenfolge. Es gibt eine Regel, die wir anwenden, wenn wir das tun. Und um die Regel anwenden zu können, müssen wir zuerst eine Frage beantworten. Nämlich: Wollen wir einen Min Heap oder einen Max Heap? Das heißt, wollen wir den niedrigsten oder den höchsten Wert auf der Oberseite des Haufens haben? Die Min Heap-Regel lautet: Ein Kind muss größer sein als sein Elternteil. Und die Max Heap-Regel lautet passend dazu: Ein Kind muss kleiner sein als sein Elternteil. Sehen wir uns das mal genauer an. Ein Heap ist eben keine voll sortierte Datenstruktur. Wir machen ein Beispiel. Wir haben jetzt zum Beispiel den obersten Wert 50. Und die Regel besagt, der nächste Wert kommt jetzt links unten, wir bekommen den Wert 100. Der passt ganz wunderbar in unsere Regel auf die linke, untere Seite. Der nächste Wert ist 75. Jetzt wäre die rechte Kindseite dran. Auch das geht sich aus, wir können also die 75 getrost auf die rechte Seite tun. Der nächste Wert, 150, passt wieder links. Der nächste Wert, 99. Wenn wir den Wert 99 jetzt wie geplant auf den nächsten freien Platz legen und das Ganze kontrollieren, dann sehen wir, dass da etwas nicht stimmen kann. Der Vorteil bei dem Heap ist jetzt, dass nicht großartig etwas passiert, außer dass genau diese zwei Objekte miteinander Platz tauschen. Damit stimmt dann die Rechnung wieder. Sehen wir uns das Ganze weiter an. Wir haben eine 76. Die passt ganz wunderbar auf den nächsten freien Platz, wie sich's gehört. Und dann haben wir die 49. Auch hier ist es wieder so: Der nächste freie Platz wäre der rechts unten. Wenn ich aber jetzt mit dem Elternteil vergleiche, merke ich, dass mein neuer Wert niedriger ist als der Elternteil. Das heißt, hier muss Platz getauscht werden. Standardmäßig wiederholt sich jetzt die Suche hin zum Elternknoten. Auch hier ist es wieder so: 49 ist niedriger als 50. Nachdem ich den niedrigsten Wert oben haben möchte, sollte ich tunlichst den Platz tauschen. So ist eigentlich sehr unspektakulär dafür gesorgt, dass immer der niedrigste Wert oben ist, oder im anderen Fall, dass immer der höchste Wert oben ist. Je nachdem, ob ich einen Min Heap oder einen Max Heap verwende. Anders als bei binären Suchbäumen haben wir hier keine spezielle Sortierung. Das einzige, worauf wir uns verlassen können, ist, dass wir immer den niedrigsten oder den höchsten Wert an oberster Stelle haben. Ein Vorteil: Ein Heap muss nicht permanent neu organisiert werden wie eine andere Datenstruktur. Ich füge einmal hinzu, ich tausche einmal den Platz, und das war's dann. Deshalb, wegen dieses garantierten oberen Werts, ist ein Heap für Priority-Queues besonders interessant. Sie erinnern sich. Bei Priority-Queues ist das einzige, was wichtig ist, dass das mit der zum Beispiel höchsten Zahl als erstes verarbeitet wird. Genau das kann ein Heap garantieren. Sehen wir uns einmal die Sprachunterstützung an. Heaps werden durch die Bank unterstützt, auch wenn sie nicht sofort als eigene Datenstruktur erkennbar sind, weil sie wie gesagt vor allem bei Priority-Queues eingesetzt werden. Prinzipiell, wie gesagt, die Unterstützung ist durchaus gut. Bei Java werden sie tatsächlich als PriorityQueue eingesetzt und in diesem Bereich verwendet. Bei C# gibt's keine Unterstützung. Bei Python gibt's eine eigene Heap Queue. Die arbeitet dann auch in der Dokumentation so beschrieben wie wir's schon kennen von unserer Priority-Queue. In Ruby gibt's keine Unterstützung. Bei Objective C gibt's wohl eine Unterstützung. Und bei C++ gibt's ein priority_queue. Ja. Das war's jetzt zum Thema Heaps. Heaps treten nicht als besondere Einzelerscheinungen vor, sondern vor allem im Zusammenhang mit dem Priority-Queues, wo sie im Hintergrund die Arbeit erledigen. Und als abstrakte Datenstruktur, die sie sind, müssen wir uns nicht weiter mit der Art und Weise auseinandersetzen, wie jetzt weiter vorgegangen wird.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!