Stapel gegen Haufen
Der Stapel ist eine geordnete Liste, in der das Einfügen und Löschen von Listenelementen nur an einem Ende erfolgen kann, das als oberste bezeichnet wird. Aus diesem Grund wird der Stapel als LIFO-Datenstruktur (Last in First out) betrachtet. Heap ist eine spezielle Datenstruktur, die auf Bäumen basiert und eine spezielle Eigenschaft erfüllt, die als Heap-Eigenschaft bezeichnet wird. Ein Heap ist auch ein vollständiger Baum, was bedeutet, dass zwischen den Blättern des Baums keine Lücken bestehen, dh in einem vollständigen Baum wird jede Ebene ausgefüllt, bevor dem Baum eine neue Ebene hinzugefügt wird und die Knoten in einer bestimmten Ebene gefüllt werden links nach rechts.
Was ist Stack?
Wie bereits erwähnt, ist Stack eine Datenstruktur, in der Elemente nur an einem Ende hinzugefügt und entfernt werden, das als oben bezeichnet wird. Stapel erlauben nur zwei grundlegende Operationen, die Push und Pop genannt werden. Die Push-Operation fügt ein neues Element oben im Stapel hinzu. Die Pop-Operation entfernt ein Element vom oberen Rand des Stapels. Wenn der Stapel bereits voll ist und eine Push-Operation ausgeführt wird, wird dies als Stapelüberlauf betrachtet. Wenn eine Pop-Operation für einen bereits leeren Stapel ausgeführt wird, wird dies als Stapelunterlauf betrachtet. Aufgrund der geringen Anzahl von Operationen, die an einem Stapel ausgeführt werden könnten, wird dies als eingeschränkte Datenstruktur betrachtet. Entsprechend der Definition der Push- und Pop-Operationen ist außerdem klar, dass Elemente, die zuletzt zum Stapel hinzugefügt wurden, zuerst aus dem Stapel entfernt werden. Daher wird der Stapel als LIFO-Datenstruktur betrachtet.
Was ist Haufen?
Wie bereits erwähnt, ist Heap ein vollständiger Baum, der die Heap-Eigenschaft erfüllt. Die Heap-Eigenschaft besagt, dass, wenn y ein untergeordneter Knoten von x ist, der in Knoten x gespeicherte Wert größer oder gleich dem in Knoten y gespeicherten Wert sein sollte (dh Wert (x) ≥ Wert (y)). Diese Eigenschaft impliziert, dass der Knoten mit dem größten Wert immer an der Wurzel platziert wird. Ein Heap, der mit dieser Eigenschaft erstellt wurde, wird als Max-Heap bezeichnet. Es gibt eine andere Variante der Heap-Eigenschaft, die das Gegenteil davon angibt. (dh Wert (x) ≤ Wert (y)). Dies impliziert, dass der Knoten mit dem kleinsten Wert immer an der Wurzel platziert wird, was als Min-Heap bezeichnet wird. Es gibt eine breite Palette von Operationen, die für Heaps ausgeführt werden, z. B. das Finden von Minimum (in Min-Heaps) oder Maximum (in Max-Heaps), Löschen von Minimum (in Min-Heaps) oder Maximum (in Max-Heaps),Erhöhen (in Max-Heaps) oder Verringern (in Min-Heaps) der Taste usw.
Was ist der Unterschied zwischen Stack und Heap?
Der Hauptunterschied zwischen Stapeln und Heaps besteht darin, dass Stack eine lineare Datenstruktur ist, Heap jedoch eine nichtlineare Datenstruktur. Der Stapel ist eine geordnete Liste, die der LIFO-Eigenschaft folgt, während der Heap ein vollständiger Baum ist, der der Heap-Eigenschaft folgt. Darüber hinaus ist Stack eine eingeschränkte Datenstruktur, die nur eine begrenzte Anzahl von Vorgängen wie Push und Pop unterstützt, während Heap eine Vielzahl von Vorgängen unterstützt, z. B. das Suchen und Löschen des Minimums oder Maximums, das Erhöhen oder Verringern des Schlüssels und das Zusammenführen.
