A Haufen ist eine vollständige binäre Baumdatenstruktur, die die Heap-Eigenschaft erfüllt: Für jeden Knoten ist der Wert seiner untergeordneten Knoten kleiner oder gleich seinem eigenen Wert. Heaps werden normalerweise zur Implementierung von Prioritätswarteschlangen verwendet, wobei sich das kleinste (oder größte) Element immer an der Wurzel des Baums befindet.

Heap-Datenstruktur

Inhaltsverzeichnis

• Arten von Haufen
• Heap-Operationen
• Was ist eine Heap-Datenstruktur?

  A Haufen ist eine binäre baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt: Der Wert jedes Knotens ist größer oder gleich dem Wert seiner untergeordneten Knoten. Diese Eigenschaft stellt sicher, dass der Wurzelknoten das enthält maximal oder Minimum Wert (abhängig von der Art des Heaps), und die Werte nehmen ab oder zu, wenn Sie sich im Baum nach unten bewegen.

  Arten von Haufen

  Es gibt zwei Haupttypen von Heaps:

  
  
  
  
  • Maximaler Haufen: Der Wurzelknoten enthält den Maximalwert und die Werte nehmen ab, wenn Sie sich im Baum nach unten bewegen.
  • Min. Heap: Der Wurzelknoten enthält den Mindestwert und die Werte erhöhen sich, wenn Sie sich im Baum nach unten bewegen.

  Heap-Operationen

  Gängige Heap-Operationen sind:

  • Einfügen : Fügt dem Heap ein neues Element hinzu und behält dabei die Heap-Eigenschaft bei.
  • Max/Min extrahieren: Entfernt das maximale oder minimale Element aus dem Heap und gibt es zurück.
  • Aufhäufen : Konvertiert einen beliebigen Binärbaum in einen Heap.

  Heaps werden üblicherweise zur Implementierung von Prioritätswarteschlangen verwendet, in denen Elemente basierend auf ihrer Priorität (Maximal- oder Minimalwert) abgerufen werden.

• Heapsort ist ein Sortieralgorithmus, der einen Heap verwendet, um ein Array in aufsteigender oder absteigender Reihenfolge zu sortieren.
• Heaps werden in Diagrammalgorithmen wie verwendet Dijkstras Algorithmus Und Prims Algorithmus zum Finden der kürzesten Pfade und minimal aufspannenden Bäume.

Binärer Heap

Anwendungen, Vor- und Nachteile von Heap

Zeitkomplexität beim Aufbau eines Heaps

Vergleich zwischen Heap und Tree

Ist die Struktur des Heaps beim Erstellen eines Heaps einzigartig?

Fibonacci-Haufen

Linker Haufen

K-ary Heap

Heap-Sortierung

Überprüfen Sie, ob ein bestimmter Binärbaum ein Heap ist

Wie überprüfe ich, ob ein bestimmtes Array einen binären Heap darstellt?

Iterative Heap-Sortierung

K'tes größtes Element in einem Array

K'tes kleinstes/größtes Element im unsortierten Array | Set 1

Höhe eines vollständigen Binärbaums (oder Heaps) mit N Knoten

Heap-Sortierung für absteigende Reihenfolge mit minimalem Heap

Gibt alle Knoten aus, die kleiner als ein Wert x sind, in einem Min Heap.

Turnierbaum (Gewinnerbaum) und binärer Heap

Verbinden Sie n Seile mit minimalen Kosten

Maximale Anzahl unterschiedlicher Elemente nach dem Entfernen von k Elementen

K maximale Summenkombinationen aus zwei Arrays

Median des Streams laufender Ganzzahlen mit STL

Median in einem Strom von ganzen Zahlen (laufende ganze Zahlen)

K'tes größtes Element in einem Stream

Größtes Triplettprodukt in einem Stream

Finden Sie k Zahlen mit den meisten Vorkommen im angegebenen Array

Konvertieren Sie den minimalen Heap in den maximalen Heap

Überprüfen Sie bei gegebener Ebenenreihenfolge eines Binärbaums, ob der Baum ein Min-Heap ist

k sortierte Arrays zusammenführen | Set 1

Sortieren Sie Nummern, die auf verschiedenen Maschinen gespeichert sind

Kleinste Störung der Reihenfolge

Größte Störung einer Sequenz

Maximaler Unterschied zwischen zwei Teilmengen von m Elementen

Konvertieren Sie BST in Min Heap

Zwei binäre Max Heaps zusammenführen

K-tes zusammenhängendes Subarray mit der größten Summe

Minimales Produkt von k Ganzzahlen in einem Array positiver Ganzzahlen

Ordnen Sie Zeichen in einer Zeichenfolge neu an, sodass keine zwei benachbarten Zeichen gleich sind

Summe aller Elemente zwischen dem k1-ten und k2-ten kleinsten Element

Minimale Summe zweier Zahlen, die aus Ziffern eines Arrays gebildet werden

Quicklinks:

• Üben Sie Probleme auf dem Heap
• Empfohlen:
  • Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial