02.03.2019
Diese Seite handelt von einer Datenstruktur namens ‘binärer Heap’ (dt. Haufen), die für das Sortieren oder als ‘Priority Queue’ (dt. Vorrangwarteschlangen) genutzt werden kann. Später mehr zu Anwendungen. Die Haupteigenschaft des Heaps ist, dass man das geringste gespeicherte Element effizient entnehmen kann. Oben können sie den binären Heap in Aktion sehen, erst werden Elemente stetig hinzugefügt, später wird das kleinste Element jeweils nach und nach entfernt. Dies sind die beiden Hauptoperationen des Heaps. Andere weniger geläufige Operationen des Heaps sind das Löschen eines beliebigen Elements, einen gespeicherten Wert zu reduzieren, oder zwei Heaps zusammenzuführen. Dieser Heap ist binär, weil jeder Knoten bis zu zwei ‘Kinder’ hat. Fortan werden wir einfach nur Heap dazu sagen. Der Heap muss allerdings nicht als Baumstruktur gespeichert werden, mehr dazu später.
Bevor es um spezifische Algorithmen für das Einfügen und Entfernen der Elemente geht, will ich die Invariante des Heaps zeigen. Dies ist eine gewissen Ordnung die zwischen Operationen aufrechterhalten werden muss.
In jeder Kette von Elementen, von der Wurzel (oben) zu einem Blatt, ist erforderlich, dass ein Kindknoten größer oder gleich seinem Elternknoten ist. Dies ist für jede Abwärtskette erforderlich, aber nebeneinander liegende Knoten müssen in keiner Relation zueinander stehen. Das kleinste Element ist ganz oben im Heap (abgesehen von dem Sonderfall, dass es mehrere gleiche kleinste Elemente gibt). Jede Operation muss diese Eigenschaft aufrechterhalten. Diese Anordnung geht darauf zurück, dass wir einen ‘Min-Heap’ zeigen. Wäre es ein ‘Max-Heap’ wäre die Anforderung, dass Kinder nicht größer als ihre Elternknoten sind, mit dem größten Element ganz oben.
Jetzt fügen wir mal ein paar Elemente in den Heap ein.
Das neue Element wird anfangs an der untersten Ebene des Binärbaums, der den Heap repräsentiert, eingefügt, und dort am rechtesten neben den anderen Elementen platziert. Dann schwebt der neue Knoten nach oben. Hinaufschweben bedeutet, dass der neue Knoten wiederholt mit seinem Elternknoten verglichen wird, und die Plätze im Baum tauscht, wenn der Neue kleiner ist als der obere Elternknoten. Dieses Vergleichen und Tauschen geht so lange, bis der Elternknoten nicht größer als die Kinder ist, oder bis das neue Element ganz oben im Baum ist. Man sieht, dass die Invariante im ganzen Heap wiederhergestellt ist.
Die nächste zu betrachtende Operation ist, das kleinste Element aus dem Heap zu entfernen. Da es sich ganz oben befindet, muss es zuerst einfach nur entfernt werden. Aber um die Invariante zu erhalten, brauchen wir ein neues oberes Element. Um dies zu erreichen, nehmen wir das letzte Element unten rechts und platzieren es ganz oben hin, gefolgt vom Herunterschweben dieses Knotens. Dazu vergleichen wir den Wert in diesem Knoten mit beiden Kinderknoten, und falls eines kleiner ist, wird der obere Knoten mit dem kleinsten der Kinder vertauscht. Das wird dann so lange wiederholt wie nötig. Der Prozess ist vorbei, wenn der Knoten kleiner oder gleich seinen beiden Kindern ist, oder wenn er ganz unten im Baum ankommt.
Obwohl der Heap am besten als Binärbaum verstanden wird, passt er ganz gut in den linearen Speicherraum, z.B. als ein Array. Man fügt ganz einfach jede Ebene des Baumes von oben nach unten, eins nach dem anderen, und jede Ebene von links nach rechts, in das Array. Die nächste freie Position um ein neues Element einzufügen, ist das ganz einfach die erste freie Position hinten im Array. Der Wurzelknoten ist dann ganz einfach das erste Element im Array. Von einer Position aus Eltern- oder Kindknoten zu finden ist dann einfach eine simple Berechnung.
Es gibt viele Anwendungen für den Heap, z.B. Pfade durch einen Graphen zu speichern, um den soweit kürzesten zu entnehmen und dort weiterzusuchen. Aber die offensichtlichste Anwendung ist das Sortieren von Zahlen: man schmeißt alle Zahlen einfach in den Heap, um sie dann eine nach der anderen in der richtigen Reihenfolge zu entnehmen. Unter den vielen Sortieralgorithmen, ist das sogenannte Heapsort unter den schnellsten. Es gibt auch eine nette Eigenschaft die manche Sortierprozeduren haben, die Fähigkeit die Sortierung in situ vorzunehmen, also ohne weiteren Speicherplatz wie ein zweites Array für die Ergebnisse. Hier präsentieren wir jetzt eine Methode um ein Array von Zahlen in situ zu sortieren, mit Hilfe der Heap Datenstruktur.
Wir beginnen mit einer Liste von Zufallszahlen, und führen die ‘Heapify’ Operation durch. Diese macht aus dem zufälligen Array einen Heap, durch Hinaufschweben der inneren Knoten bis die Invariante erfüllt ist. Als nächstes kommt die Sortierphase, bei der das Wurzelelement ans Ende des Arrays platziert wird, an den Platz der gerade durch die Entfernenoperation frei geworden ist. Dieser vormalig am Ende des Arrays frei werdende Platz wird nach und nach mit den sortierten Zahlen gefüllt. Da wir einen Min-Heap benutzt haben, erhalten wir ein absteigend sortiertes Array. Mit einem Max-Heap hätten wir hingegen eine aufsteigende Ordnung erhalten.
Was ist also der Sinn darin den Heap zu verwenden, anstelle einer einfachen Liste oder einer anderen Datenstruktur? Die Antwort darauf findet sich in der Performanz des Heaps in Sachen Zeitaufwand bei den wesentlichen Operationen. Wenn man die Binärbäume anschaut fällt einem auf, dass jede Ebene doppelt sie viele Knoten aufnehmen kann wie die vorherige. Die erforderliche Tiefe des Baumes geht also logarithmisch mit der Gesamtzahl der Knoten rauf. Die Tiefe wächst also eher langsam mit der Zahl an gespeicherten Elementen. Und die Zeit die für das Hinauf- und Hinabschweben gebraucht wird ist eine Funktion der Tiefe des Baumes. Egal wie viele Elemente im Heap sind, der Aufwand für das Einfügen und Entfernen ist proportional zum Logarithmus der Größe, also nur von der Größenordnung des Baumes abhängig.
Ich hoffe ihnen hat diese animierte Erklärung der Heap Datenstruktur gefallen, es gibt mehr Inhalte auf unserer Homepage zu entdecken.