Haufen vs. Stapel: Was unterscheidet sie?
Als Programmierer sind Sie wahrscheinlich schon auf die Begriffe „Heap“ und „Stack“ gestoßen. Es ist eine weit verbreitete Praxis für Anfänger, diese beiden Begriffe synonym und falsch zu verwenden.
Während Studenten eines Kurses zu Datenstrukturen und erfahrene Programmierer leicht zwischen diesen beiden Datenstrukturen unterscheiden können, können sie für andere gleich erscheinen.
Programmierer müssen zwischen den beiden unterscheiden und sie in praktischen Programmiersituationen angemessen verwenden. Interviewer sind oft daran interessiert, Bewerbern ein Szenario zu geben und dann nach der am besten geeigneten Datenstruktur zu fragen.
Lesen Sie weiter, während wir einen detaillierten Blick auf Heaps, Stacks, deren Unterschiede und relevante Anwendungen werfen.
Was ist ein Haufen?
Ein Heap für Programmierer ist typischerweise eine spezielle Baumdatenstruktur, die oft als "Prioritätswarteschlange" bezeichnet wird. Heaps, die eine vollständig ausgeglichene Binärbaumstruktur sind (denken Sie daran, dass alle Ebenen eines vollständigen Binärbaums gefüllt sind, außer der letzten Ebene) und einer Heap-Eigenschaft folgen, werden Binäre Heaps genannt.
Die Heap-Eigenschaft strukturiert den Baum so, dass der maximale oder der minimale Wert an der Wurzel platziert wird.
In einem Max Heap ist der Wert der übergeordneten Knoten größer als der der untergeordneten Knoten, und die Wurzel des Baums enthält den maximalen Wert. Alternativ ist ein Min Heap so strukturiert, dass er den minimalen Wert als Wurzel hat, und jeder Kindknoten hat einen größeren Wert als sein Elternknoten. Die Heap-Eigenschaft muss für jeden Knoten im Binärbaum rekursiv wahr sein.
Heaps werden im Allgemeinen durch lineare Arrays implementiert, wobei das erste Element des Arrays ( Arr[0] ) die Wurzel darstellt. Für einen bestimmten Knoten i können Sie die Kindknoten bei Arr[ (2*i) + 1 ] und Arr[ (2*i) + 2] abrufen, ähnlich befindet sich der Elternknoten bei Arr[ (i-1) /2 ] -Index. Die meisten Sprachen wie Java und C++ enthalten Bibliotheken, die Benutzern gebrauchsfertige Min- und Max-Heaps bereitstellen.
Was ist ein Stapel?
Stacks sind eine der ersten Datenstrukturen, die den Schülern beigebracht werden, und sie sollten nicht übersehen werden. Ein Stack ist eine Datenstruktur, die sich wie jeder reale Stack (Karten, Platten usw.) verhält. Stacks erlauben Operationen nur an einem Ende und haben daher eine LIFO-Charakteristik (Last-In-First-Out). Im Gegensatz dazu haben Warteschlangen eine FIFO-Eigenschaft (First-In-First-Out) und erlauben Operationen an beiden Enden.
Typische Stack-Operationen bestehen aus Push (Einfügen von Daten oben in den Stack) und Pop (Entfernen des obersten Datenelements). Sie können Stacks je nach Ihren Anforderungen durch Zeiger, Arrays oder sogar verknüpfte Listen implementieren. C++, C# und Java enthalten alle Bibliotheken, die bereits einen Stack implementiert haben, sodass Sie sie jederzeit verwenden können.
Haufen vs. Stapel
Wenn Sie bis hierher gelesen haben, haben Sie eine ziemlich gute Vorstellung von den Unterschieden zwischen einem Stapel und einem Heap. Stapel sind linear und haben eine LIFO-Charakteristik, während Heaps eine Baumstruktur haben und der Heap-Eigenschaft folgen. Beide haben unterschiedliche Anwendungen, die wir im nächsten Abschnitt besprechen werden.
In Bezug auf eine asymptotische Zeitkomplexitätsanalyse können Sie einen binären Heap in O(n) aufbauen und den minimalen oder maximalen Wert in O(1) extrahieren. Einfügungen und Löschungen können in O(log N)-Zeit erreicht werden. Im Gegensatz dazu dauert das Einfügen und Löschen in einem Stack O(1) Zeit.
Typische Anwendungen
Aus den oben erörterten Gründen sind Heaps sehr effizient, wenn sie als Prioritätswarteschlange verwendet werden. Graphalgorithmen wie der Minimum Spanning Tree von Prim und der Shortest Path von Dijkstra verwenden typischerweise Heaps als Prioritätswarteschlange. Eine weitere wichtige Anwendung von Heaps ist das effiziente Sortieren eines Arrays in nur O(N logN) Zeit; diese Sortiertechnik ist als "Heap Sort" bekannt.
Auch Stacks haben eine Vielzahl von kritischen Anwendungen wie Speicherverwaltung und Ausdrucksauswertung. Wenn Sie mit einem Backtracking-Codierungsproblem konfrontiert sind, ist es möglicherweise eine gute Idee, mit einem Stack den Tag zu retten.
Datenstrukturen priorisieren
Jeder erfolgreiche Programmierer wird Ihnen sagen, wie wichtig es ist, mit Datenstrukturen vertraut zu werden. Es ist eine großartige Idee, zu versuchen, verschiedene Datenstrukturen nach Bedarf zu verstehen und sich damit vertraut zu machen, da dies ein wichtiges Konzept für jeden Programmierer da draußen ist.