Inhaltsverzeichnis:
Definition - Was bedeutet Heap?
Ein Heap im Kontext der Datenstruktur ist eine baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt, bei der jedem Element ein Schlüsselwert oder eine Gewichtung zugewiesen wird. Der Schlüssel mit dem niedrigeren Wert hat immer einen übergeordneten Knoten mit einem Schlüssel mit dem höheren 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, wobei ein Element mit einem Schlüssel mit höherem Wert immer einen Schlüssel mit niedrigerem Wert als übergeordneter Knoten hat. Dies wird als Min-Heap-Struktur bezeichnet, und unter allen Knoten hat der Stammknoten den niedrigsten Schlüssel.
Techopedia erklärt Heap
Es gibt keine praktischen Einschränkungen für die Anzahl der untergeordneten Elemente, die jeder Knoten in einem Heap haben kann, obwohl jeder Knoten normalerweise höchstens zwei hat. Der Heap wird als effizienteste Implementierung eines abstrakten Datentyps angesehen, der als Prioritätswarteschlange bezeichnet wird. Die Implementierung des Heapspeichers ist sowohl in verschiedenen Grafikalgorithmen (einschließlich des Dijkstra-Algorithmus) als auch im Heapsort-Sortieralgorithmus von wesentlicher Bedeutung.
Heaps weisen mehrere Varianzen auf, die als Prioritätswarteschlangenimplementierungen für abstrakte Datentypen mit hoher Effizienz fungieren. Viele Anwendungen, wie z. B. Graph-Algorithmen, erfordern die Implementierung von Prioritätswarteschlangen.
Ein Array ist die häufigste Implementierungsform eines Heapspeichers, bei der keine Zeiger zum Verknüpfen der Elemente erforderlich sind.
Heaps führen mehrere Operationen aus, darunter:
- Find-max: Sucht nach dem höchsten Schlüsselknoten aus einer Gruppe von Knoten
- Find-min: Sucht nach dem niedrigsten Schlüsselknoten aus einer Gruppe von Knoten
- Delete-Max: Löscht den höchsten Schlüsselknoten aus einer Gruppe von Knoten
- Delete-min: Löscht den untersten Schlüsselknoten aus einer Gruppe von Knoten
Zu den Heaps gehören auch Funktionen zum Zusammenführen, Einfügen und Ändern von Schlüsseln.
Diese Definition wurde im Kontext der Datenstruktur geschrieben
