Haufen

Definition - Was bedeutet Heap?

Ein Heap ist im Kontext der Datenstruktur eine baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt, wobei jedem Element ein Schlüsselwert oder eine Gewichtung zugewiesen wird. Der Schlüssel mit niedrigerem Wert hat immer einen übergeordneten Knoten mit einem Schlüssel mit höherem Wert. Dies wird als Max-Heap-Struktur bezeichnet, und unter allen Knoten hat der Stammknoten den höchsten Schlüssel.

Manchmal hat eine baumbasierte Struktur eine umgekehrte Strukturregel, bei der ein Element mit einem Schlüssel mit höherem Wert immer einen Schlüssel mit niedrigerem Wert als übergeordneten Knoten hat. Dies wird als Min-Heap-Struktur bezeichnet, und unter allen Knoten hat der Stammknoten den niedrigsten Schlüssel.

Technische.me erklärt Heap

Es gibt keine praktischen Einschränkungen hinsichtlich der Anzahl der untergeordneten Knoten, die jeder Knoten in einem Heap haben kann, obwohl jeder Knoten normalerweise höchstens zwei hat. Der Heap wird als die effizienteste Implementierung eines abstrakten Datentyps angesehen, der als Prioritätswarteschlange bezeichnet wird. Die Heap-Implementierung ist sowohl in verschiedenen Graph-Algorithmen (einschließlich des Dijkstra-Algorithmus) als auch im Heapsort-Sortieralgorithmus von wesentlicher Bedeutung.

Heaps weisen mehrere Varianzen auf, die als Implementierungen von Prioritätswarteschlangen für abstrakte Datentypen mit hoher Effizienz fungieren. Viele Anwendungen, wie z. B. Diagrammalgorithmen, erfordern die Implementierung von Prioritätswarteschlangen.

Ein Array ist die häufigste Implementierungsform von Heap, bei der keine Zeiger zum Verknüpfen seiner Elemente erforderlich sind.

Heaps führen mehrere Operationen aus, einschließlich:

  • Find-max: Sucht nach dem höchsten Schlüsselknoten unter einer Gruppe von Knoten
  • Find-min: Sucht nach dem niedrigsten Schlüsselknoten unter einer Gruppe von Knoten
  • Delete-max: Löscht den höchsten Schlüsselknoten unter einer Gruppe von Knoten
  • Delete-min: Löscht den niedrigsten Schlüsselknoten unter einer Gruppe von Knoten

Heaps enthalten auch Funktionen zum Zusammenführen, Einfügen und Ändern von Schlüsseln.

Diese Definition wurde im Kontext der Datenstruktur geschrieben