Die Verwendung von Datenstrukturen ist im Bereich der Computerprogrammierung von entscheidender Bedeutung, insbesondere wenn es darum geht, Daten schnell und effizient zu speichern, zu verwalten und zu organisieren. Jeder Entwickler muss die Datenstruktur gründlich verstehen, da sie seine Fähigkeiten erheblich verbessern kann. Min- und Max-Heap-Implementierung sind ein wichtiger Teil der Datenstruktur und jeder sollte sich mit ihnen vertraut machen.
Verstehen, was Heap ist
Heap ist im Kern eine fortschrittliche baumbasierte Datenstruktur, die Programmierer hauptsächlich zur Implementierung und Sortierung von Warteschlangen verwenden. Heaps sind binäre Bäume, und hier sind ihre wichtigsten Merkmale:
- Die Einstiegsebene in Heaps ist gefüllt, wobei die Blattknoten die Ausnahme bilden
- Alle Knoten haben maximal 2 Kinder
- Jeder Knoten befindet sich ganz links, d. h. jedes Kind befindet sich links von seinem Elternteil.
Heaps verwenden binäre Bäume, um Löcher im Array zu vermeiden. Binäre Bäume sind Bäume, in denen jeder Knoten zwei Kinder hat und jeder Knoten voll ist, mit Ausnahme der Blattknoten, die leer sind. Heaps werden über ihre Eigenschaft erstellt. Die Eigenschaft vergleicht im Wesentlichen die Eltern mit den Schlüsseln ihrer Kindknoten.
Denken Sie daran, dass Heaps nicht immer sortiert sind und einer Schlüsselbedingung folgen, bei der das kleinste oder größte Element auf dem Wurzelknoten vorhanden ist, je nachdem, ob es sich um einen Min- oder Max-Heap handelt.
Vorteile und Nachteile von Haufen
Vorteile
- Sie können global auf Variablen zugreifen
- Haufen sind sehr nützlich, um die größten und kleinsten Zahlen zu finden
- Haufen sind in der Regel unglaublich flexibel, und Sie können sie in beliebiger Reihenfolge entfernen oder zuordnen
Beeinträchtigungen
- Heaps benötigen im Vergleich zu Stacks viel mehr Ausführungszeit
- Die von Heaps benötigte Berechnungszeit ist im Allgemeinen höher
- Die Verwaltung des Speichers kann mit dem Heap-Speicher eine ziemliche Herausforderung darstellen. Der Grund dafür ist, dass Heap überall auf der Welt verwendet wird.
Heap-Datenstruktur-Anwendungen
Heaps sind unglaublich effizient, wenn es darum geht, das maximale oder minimale Element in Arrays zu finden. Sie sind auch bei Auswahlalgorithmen und Statistiken nützlich. Die Zeitkomplexität für die Verwendung von Heaps zur Gewinnung von Maximal- oder Minimalwerten beträgt O(1)O(1).
Programmierer entwerfen Prioritäts-Warteschlangen auf der Grundlage der Strukturen des Heaps. Es dauert etwa O(log(n))O(log(n)), um jedes Element in der Prioritätswarteschlange mit maximaler Effizienz einzufügen und zu löschen.
Prioritäts-Warteschlangen (Heap-implementiert) finden sich häufig in Algorithmen wie z. B.:
- Der Heapsort-Algorithmus
- Dijkstra-Algorithmus
- Prims Algorithmus
Wesentliche Heap-Operationen
Im Folgenden sind die wichtigsten Operationen aufgeführt, die bei der Einbeziehung von Heap-Datenstrukturen verwendet werden.
getMax(): Mit dieser Operation wird der maximale Wert im Heap zurückgegeben
Größe: Die Operation size wird verwendet, um die Größe des Heaps zu ermitteln.
extract: Extract hilft, den Wert eines Elements zurückzugeben und es anschließend aus dem Heap zu löschen
löschen: Delete wird zum Entfernen von Elementen auf einem Heap verwendet
einfügen: Dieser Befehl fügt Elemente in den Heap ein und behält seine Eigenschaft bei.
heapify: Heapify ordnet die Elemente des Heaps neu an, um die Eigenschaften des Heaps zu erhalten.
Schritte zum Aufbau von Max Heap
Jedes Element in max heap neigt dazu, nach der max heap-Eigenschaft zu handeln, was bedeutet, dass der Schlüssel des übergeordneten Knotens jedes Mal größer ist als der Schlüssel des untergeordneten Knotens. Befolgen Sie diese Schritte, um max heap richtig aufzubauen:
- Einen neuen Knoten an der ursprünglichen Wurzel des Sprungs bilden
- Geben Sie ihm einen Wert
- Nach der Zuweisung eines Wertes werden die Werte des übergeordneten und des untergeordneten Knotens verglichen
- Falls der übergeordnete Knoten niedriger ist als ein untergeordneter Knoten, tauschen Sie die Knoten
- Wiederholen Sie den Schritt, bis das größte Element die übergeordneten Knoten der Wurzel erreicht
Sie können diese Schritte auch befolgen, wenn Sie neue Elemente in einen Haufen einfügen. Denken Sie daran, dass unabhängig von der Art der Operation, die Sie auf einem Max Heap durchführen, die Erhaltung der Heap-Eigenschaften von entscheidender Bedeutung ist.
Schritte zum Löschen/Entfernen von Knoten in Max Heap
Die unten aufgeführten Schritte helfen Ihnen, Max Heap Nodes effektiv zu entfernen oder zu löschen:
- Den letzten untergeordneten Knoten in die letzte Ebene der Wurzel verschieben
- Vergleichen Sie die Kind- und Elternknoten
- Wenn der Wert des Elternteils niedriger ist als der des Kindes, wäre es am besten, die beiden zu tauschen und dann den Vorgang zu wiederholen, bis der Heap voll ist.
Wie bereits erwähnt, müssen Sie sich mit den verschiedenen Datenstrukturen vertraut machen und wissen, wie Sie am besten an komplexe Fragen der Programmierung herangehen. Dies wird Ihnen auch dabei helfen, eine klare Vorstellung von der Min- und Max-Heap-Implementierung zu bekommen und sicherzustellen, dass Sie diese ohne Probleme nutzen können.
Schritte zum Aufbau von Min Heap
Die Elemente im Min-Heap verhalten sich im Allgemeinen entsprechend der Eigenschaft des Min-Heap, die sich stark von der Funktionsweise des Max-Heap unterscheidet. Denken Sie daran, dass der Schlüssel des übergeordneten Knotens immer kleiner ist als der Schlüssel des untergeordneten Knotens. Die folgenden Schritte können Ihnen bei der Erstellung eines min heap helfen:
- Bildung eines neuen untergeordneten Knotens auf der untersten Ebene, d. h. am Ende des Heaps
- Einfügen des neuen Schlüssels in den Knoten
- Beginnen Sie, das Kind nach oben zu verschieben, und stellen Sie sicher, dass Sie die Heap-Eigenschaft erfüllen, wenn Sie den Wurzelknoten erreichen
Schritte zum Löschen oder Entfernen von Rood-Knoten im Min-Heap
- Fahren Sie fort, indem Sie einfach den Wurzelknoten löschen
- Den Schlüssel des letzten Kindes zur Wurzel verschieben
- Durchführung einer vergleichenden Analyse zwischen dem Knoten und seinen Kindern
- Wenn der Wert des übergeordneten Knotens höher ist als der der untergeordneten Knoten, tauschen Sie diese aus, indem Sie den Vorgang so lange wiederholen, bis Sie die Heap-Eigenschaft erfüllen
Warum Haufen wichtig sind
Es ist zwar schön und gut zu verstehen, wie die Min- und Max-Heap-Implementierung funktioniert, aber Sie müssen auch den Grund erfahren, warum Heaps so wichtig sind. Zunächst einmal haben Programmierer Heaps in Betriebssystemen für die Arbeitsplanung verwendet, um sicherzustellen, dass Arbeitgeber die Mitarbeiter nach Priorität anrufen können. Sie finden Heaps auch in verschiedenen Heap-Sortieralgorithmen für die Implementierung von Prioritätswarteschlangen. Auch der Dijkstra-Algorithmus nutzt Heaps, um kurze Wege zu ermitteln.