Heap-Datenstruktur: Was ist ein Heap?

Was ist eine Heap-Datenstruktur?

Ein Heap ist eine spezielle baumbasierte Datenstruktur. Er besteht aus einem obersten Knoten, der Wurzel (Elternknoten). Der zweite Knoten ist das linke Kind der Wurzel, der dritte das rechte. Die nachfolgenden Knoten werden von links nach rechts befüllt. Der Schlüssel jedes Elternknotens wird mit dem Schlüssel seiner Kinder verglichen, um eine korrekte Anordnung zu gewährleisten. Der Baum ist leicht zu visualisieren: Jede Einheit wird als Knoten bezeichnet, und jeder Knoten besitzt einen eindeutigen Schlüssel zur Identifizierung.

Vereinfacht ausgedrückt ist ein Heap ein vollständiger Binärbaum, der die Heap-Eigenschaft erfüllt: Jeder Elternknoten ist konsistent mit seinen Kindern geordnet, was ihn ideal für Prioritätswarteschlangen und Heapsort macht.

Warum benötigen Sie eine Heap-Datenstruktur?

Hier sind die Hauptgründe für die Verwendung eines Heaps:

• Die Heap-Datenstruktur ermöglicht das Löschen und Einfügen in logarithmischer Zeit – O(log₂n.).
• Die Daten im Baum sind in einer bestimmten Reihenfolge angeordnet. Neben dem Aktualisieren oder Abfragen von Werten wie Maximum oder Minimum kann der Programmierer auch Beziehungen zwischen Eltern- und Tochterknoten ermitteln.
• Sie können das Konzept des anwenden Dokumentobjektmodell um Ihnen das visuelle Verständnis der Heap-Datenstruktur zu erleichtern.
• Heaps unterstützen effiziente Prioritätswarteschlangenoperationen, die für Graphalgorithmen wie Dijkstras kürzesten Pfad und Prims minimalen Spannbaum von entscheidender Bedeutung sind.

Arten von Haufen

Die Heap-Datenstruktur verfügt über verschiedene Algorithmen zum Einfügen und Entfernen von Elementen, darunter Prioritätswarteschlange, Binär-Heap, Binomial-Heap und Haufen sortieren.

• Prioritätswarteschlange: Es ist ein AbstracDie Datenstruktur enthält priorisierte Objekte. Jedem Objekt oder Element ist eine Priorität zugewiesen. Daher wird das Objekt oder Element mit der höheren Priorität vor den übrigen bedient.
• Binärer Heap: Binäre Heaps eignen sich für einfache Heap-Operationen wie Löschungen und Einfügungen. Sie sind die Standardimplementierung der meisten Prioritätswarteschlangen der Standardbibliothek.
• Binomialhaufen: Ein Binomial-Heap besteht aus einer Reihe von Binomialbäumen, die den Heap bilden. Ein Binomial-Heap-Baum ist kein gewöhnlicher Baum, da er streng definiert ist. Die Gesamtzahl der Elemente in einem Binomialbaum beträgt immer 2ⁿ.ⁿ Knoten.
• Heap-Sortierung: Im Gegensatz zu den meisten Sortieralgorithmen benötigt Heap Sort O(1) Speicherplatz für seine Sortieroperation. Es handelt sich um einen vergleichsbasierten Sortieralgorithmus, bei dem die Sortierung in aufsteigender Reihenfolge erfolgt, indem die Eingabe zunächst in einen Max-Heap umgewandelt wird. Man kann Heap Sort als eine erweiterte Version eines binären Suchbaums betrachten.

Typischerweise verwendet eine Heap-Datenstruktur zwei Strategien. Für die Eingabe 12 – 8 – 4 – 2 und 1:

• Min-Heap – geringster Wert oben
• Max-Heap – höchster Wert oben

Min-Heap

In der Min-Heap-Struktur hat der Wurzelknoten einen Wert, der gleich oder kleiner als der Wert seiner Kinderknoten ist. Die Wurzel eines Min-Heaps enthält somit den Minimalwert. Der Min-Heap ist außerdem ein vollständiger Binärbaum.

Sobald ein Min-Heap in einem Baum existiert, kommen alle Blätter als Kandidaten für den Maximalwert in Frage. Um jedoch den exakten Max-Heap-Wert zu ermitteln, muss jedes Blatt untersucht werden.

Min-Heap-Beispiel

Im obigen Diagramm ist eine klare Sequenz von der Wurzel bis zum untersten Knoten erkennbar.

Angenommen, Sie speichern die Elemente im Array Array_N[12, 2, 8, 1, 4]. Wie Sie dem Array entnehmen können, verstößt das Wurzelelement gegen die Min-Heap-Priorität. Um die Min-Heap-Eigenschaft zu erhalten, müssen Sie die Min-Heapify-Operationen durchführen, um die Elemente so lange zu vertauschen, bis die Min-Heap-Regeln erfüllt sind.

Max-Heap

In der Max-Heap-Struktur besitzt der Elternknoten (Wurzelknoten) einen Wert, der gleich oder größer als der Wert seiner Kinder ist. Dieser Knoten enthält den Maximalwert. Da es sich um einen vollständigen Binärbaum handelt, lässt sich ein Max-Heap aus einer Menge von Werten in O(n) Zeit aufbauen.

Hier sind einige Methoden, die üblicherweise bei der Implementierung von Java Max-Heap:

• Hinzufügen (): Fügt ein neues Element in einen Heap ein. Bei Verwendung eines Arrays werden die Objekte am Ende des Arrays hinzugefügt, während sie im Binärbaum von oben nach unten und dann von links nach rechts eingefügt werden.
• Entfernen (): Diese Methode ermöglicht es Ihnen, das erste Element aus der Array-Liste zu entfernen. Da das neu verschobene Element nicht mehr das größte ist, verschiebt die Sift-Down-Methode es immer an seine neue Position.
• Sift-Down (): Diese Methode vergleicht ein Wurzelobjekt mit seinen Kindobjekten und verschiebt dann den verschobenen Knoten an seine richtige Position.
• Sift-Up (): Wenn Sie die Array-Methode verwenden, um ein neues Element zu einem Array hinzuzufügen, hilft die Sift-Up-Methode dem neu hinzugefügten Knoten dabei, an die richtige Position zu gelangen. Das neue Element wird zunächst mit seinem übergeordneten Element verglichen, indem die Baumstruktur simuliert wird.

  Wende die Formel Parent_Index = Child_Index / 2 an. Fahre damit fort, bis sich das größte Element am Anfang des Arrays befindet.

Grundlegender Heap Operations

Um die höchsten und niedrigsten Werte in einem Datensatz zu finden, benötigen Sie einige grundlegende Heap-Operationen wie Suchen, Einfügen und Löschen. Da Elemente ständig hinzugefügt und entfernt werden, sollten Sie Folgendes wissen:

• Finde – Suchen Sie nach einem Gegenstand auf einem Haufen.
• Insert – Fügen Sie dem Heap ein neues Kind hinzu.
• Löschen – Löschen Sie einen Knoten aus einem Heap.

Erstellen Sie Haufen

Der Prozess des Aufbaus von Heaps wird als Heap-Erstellung bezeichnet. Ausgehend von einer Liste von Schlüsseln erstellt der Programmierer einen leeren Heap und fügt dann die übrigen Schlüssel nacheinander mithilfe der grundlegenden Heap-Operationen ein.

Beginnen wir also mit dem Aufbau eines Min-Heaps nach Williams Methode, indem wir die Werte 12, 2, 8, 1 und 4 einfügen. Man kann den Heap mit n Elementen aufbauen, indem man mit einem leeren Heap beginnt und ihn dann sukzessive mit anderen Elementen füllt. Die Laufzeit beträgt O(n log n).

• Heapify: Eine Einfügeroutine, die dabei hilft, Elemente in einen Heap einzufügen und gleichzeitig die Heap-Eigenschaften zu erhalten.

  Eine Max-Heapify-Operation prüft beispielsweise, ob der Wert des Elternelements größer ist als der seiner Nachkommen. Die Elemente können dann mithilfe von Methoden wie `swap` sortiert werden.ping.

• Verschmelzen: Wenn Sie zwei Heaps zu einem einzigen zusammenführen möchten, verwenden Sie die Merge-Operation, um die Werte der beiden Heaps zusammenzuführen. Die ursprünglichen Heaps bleiben dabei erhalten.

Inspizieren Sie Haufen

Bei der Heap-Inspektion geht es darum, die Anzahl der Elemente in der Heap-Datenstruktur zu überprüfen und festzustellen, ob der Heap leer ist.

Beim Sortieren oder Einreihen von Elementen ist es wichtig, den Heap zu überprüfen. Die Prüfung, ob Elemente zur Verarbeitung vorhanden sind, ist mit `Is-Empty()` wichtig. Die Heap-Größe hilft, die Wurzeln des Max-Heaps bzw. Min-Heaps zu finden. Daher muss bekannt sein, wie viele Elemente der Heap-Eigenschaft folgen.

• Größe – Gibt die Größe oder Länge des Heaps zurück. Sie gibt an, wie viele Elemente in sortierter Reihenfolge gespeichert sind.
• Ist-Leer – gibt TRUE zurück, wenn der Heap null ist, andernfalls gibt er FALSE zurück.

Hier drucken Sie alle Elemente im PrioritätQ Schleife ausführen und dann überprüfen, ob PriorityQ nicht leer ist.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Verwendung der Heap-Datenstruktur

Die Heap-Datenstruktur ist in vielen Programmieranwendungen im realen Leben nützlich, zum Beispiel:

• Hilft bei der Spamfilterung.
• Implementierung von Graphalgorithmen wie Dijkstra und Prim.
• OperaLastverteilung und Datenkomprimierung des Ting-Systems.
• Bestimmung von Ordnungsstatistiken wie dem k-kleinsten Element.
• Implementierung von Prioritätswarteschlangen, mit denen man Elemente in einer Liste in logarithmischer Zeit suchen kann.
• Die Heap-Datenstruktur wird auch zum Sortieren mittels Heap Sort verwendet.
• Simulation von Kunden in einer Warteschlange.
• Interruptbehandlung in der Betriebssystem.
• Bei der Huffman-Codierung zur Datenkomprimierung.
• Unterstützung der Best-First-Suche und der A*-Heuristik in der KI-Pfadplanung.

Eigenschaften der Heap-Prioritätswarteschlange

Die folgenden Eigenschaften beschreiben das Verhalten der auf einem Heap aufgebauten Prioritätswarteschlange:

• Bei Prioritäts-Heaps werden die Datenelemente in der Liste miteinander verglichen, um das kleinere oder größere Element zu bestimmen.
• Ein Element wird in eine Warteschlange gestellt und anschließend in der Reihenfolge seiner Priorität entfernt.
• Jedem einzelnen Element in der Prioritätswarteschlange ist eine eindeutige Nummer zugeordnet, die seine Priorität angibt.
• Beim Verlassen einer Prioritätswarteschlange wird das Element mit der höchsten Priorität zuerst verlassen.

Schritte zur Implementierung der Heap-Prioritätswarteschlange in Java

Der nächste Abschnitt führt in einen Beton Java Implementierung, die diese Regeln in funktionierenden Code umsetzt.

Heapsort in Java und Code Beispiel

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Ausgang

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Heapsort in Python und Code Beispiel

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Ausgang

[1, 3, 4, 7, 9]

Als Nächstes erfahren Sie mehr über die Bisektionsmethode.

Häufig gestellte Fragen