Heap-Datenstruktur: Was ist Heap? Min. und Max. Heap (Beispiel)

Was ist ein Heap?

Heap ist eine spezialisierte Baumdatenstruktur. Der Heap besteht aus dem obersten Knoten, der als Wurzel (übergeordnet) bezeichnet wird. Sein zweites Kind ist das linke Kind der Wurzel, während der dritte Knoten das rechte Kind der Wurzel ist. Die aufeinanderfolgenden Knoten werden von links nach rechts gefüllt. Der Schlüssel des übergeordneten Knotens wird mit dem seines untergeordneten Knotens verglichen, und es entsteht eine ordnungsgemäße Anordnung. Der Baum lässt sich leicht visualisieren, wobei jede Entität als Knoten bezeichnet wird. Der Knoten verfügt über eindeutige Schlüssel zur Identifizierung.

Warum benötigen Sie eine Heap-Datenstruktur?

Hier sind die Hauptgründe für die Verwendung der Heap-Datenstruktur:

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 Dingen wie einem Maximum oder Minimum kann der Programmierer Beziehungen zwischen dem Elternteil und dem Nachkommen finden.
Sie können das Konzept des anwenden Dokumentobjektmodell um Ihnen beim Verständnis der Heap-Datenstruktur zu helfen.

Arten von Haufen

Die Heap-Datenstruktur verfügt über verschiedene Algorithmen zum Verarbeiten von Einfügungen und Entfernen von Elementen in einer Heap-Datenstruktur, darunter Priority-Queue, Binary-Heap, Binomial Heap und Heap-Sortierung.

Prioritätswarteschlange: Es handelt sich um eine abstrakte Datenstruktur, die priorisierte Objekte enthält. Für jedes Objekt oder Element ist eine Priorität festgelegt. Daher erhält das Objekt oder Element, dem die höhere Priorität zugewiesen wurde, den Service vor den anderen.
Binär-Heap: Binäre Heaps eignen sich für einfache Heap-Operationen wie Löschungen und Einfügungen.
Binomial-Heap: Ein Binomial-Heap besteht aus einer Reihe von Sammlungen von Binomialbäumen, aus denen der Heap besteht. Binomial-Heap-Baum ist kein gewöhnlicher Baum, wie er streng definiert ist. Die Gesamtzahl der Elemente in einem Binomialbaum beträgt immer 2ⁿ Knoten.
Heap-Sortierung: Im Gegensatz zu den meisten Sortieralgorithmen verwendet Heapsort für seine Sortieroperation O(1) Speicherplatz. Es handelt sich um einen vergleichsbasierten Sortieralgorithmus, bei dem die Sortierung in aufsteigender Reihenfolge erfolgt, indem zunächst ein maximaler Heap erstellt wird. Sie können Heapsort als einen qualitativ verbesserten binären Suchbaum betrachten.

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

Min. Heap – kleinster Wert oben
Max Heap – höchster Wert oben

Min. Haufen

In der Min-Heap-Struktur hat der Wurzelknoten einen Wert, der entweder gleich oder kleiner als der Wert der untergeordneten Knoten auf diesem Knoten ist. Dieser Heap-Knoten eines Min-Heaps enthält den Mindestwert. Alles in allem ist seine Min-Heap-Struktur vollständig binärer Baum.

Sobald Sie einen Min-Haufen in einem Baum haben, sind alle Blätter brauchbare Kandidaten. Sie müssen jedoch jedes Blatt untersuchen, um den genauen Max-Heap-Wert zu erhalten.

Beispiel für einen minimalen Heap

In den obigen Diagrammen können Sie eine klare Reihenfolge von der Wurzel bis zum untersten Knoten erkennen.

Angenommen, Sie speichern die Elemente im Array Array_N[12,2,8,1,4]. Wie Sie dem Array entnehmen können, verletzt das Stammelement die Min-Heap-Priorität. Um die Min-Heap-Eigenschaft beizubehalten, müssen Sie die Min-Heapify-Operationen ausführen, um die Elemente auszutauschen, bis die Min-Heap-Eigenschaften erfüllt sind.

Max. Haufen

In der Struktur von Max Heap hat der übergeordnete oder Wurzelknoten einen Wert, der gleich oder größer als der Wert seiner untergeordneten Knoten im Knoten ist. Dieser Knoten enthält den Maximalwert. Darüber hinaus handelt es sich um einen vollständigen Binärbaum, sodass Sie aus einer Sammlung von Werten einen maximalen Heap erstellen und diesen mit O(n)-Zeit ausführen können.

Hier sind einige Methoden zum Implementieren eines Java-Max-Heaps

Hinzufügen (): Platzieren Sie ein neues Element in einem Heap. Wenn Sie ein Array verwenden, werden die Objekte am Ende des Arrays hinzugefügt, während im Binärbaum die Objekte von oben nach unten und dann von links nach rechts hinzugefügt werden.
Entfernen (): Mit dieser Methode können Sie das erste Element aus der Array-Liste entfernen. Da das neu hinzugefügte Element nicht mehr das größte ist, verschiebt es die Sift-Down-Methode immer an seine neue Position.
Heruntersieben (): Diese Methode vergleicht ein Stammobjekt mit seinem untergeordneten Objekt und verschiebt dann den neu hinzugefügten Knoten an seine rechtmäßige Position.
Sift-Up (): Wenn Sie die Array-Methode verwenden, um ein neu eingefügtes Element zu einem Array hinzuzufügen, hilft die Sift-Up-Methode dabei, den neu hinzugefügten Knoten an seine neue Position zu verschieben. Das neu eingefügte Element wird zunächst durch Simulation der Baumdatenstruktur mit dem übergeordneten Element verglichen.
Wenden Sie die Formel Parent_Index=Child_Index/2 an. Dies machen Sie so lange, bis sich das maximale Element am Anfang des Arrays befindet.

Grundlegender Heap Operations

Um die höchsten und niedrigsten Werte in einem Datensatz zu finden, benötigen Sie viele grundlegende Heap-Operationen wie Suchen, Löschen und Einfügen. Da Elemente ständig kommen und gehen, müssen Sie:

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 der Heap-Konstruktion wird als Heap-Erstellung bezeichnet. Aus einer gegebenen Liste von Schlüsseln erstellt der Programmierer einen leeren Heap und fügt dann mithilfe grundlegender Heap-Operationen nacheinander weitere Schlüssel ein.

Beginnen wir also mit dem Aufbau eines Min-Heaps mit der Methode von Willaim, indem wir die Werte 12,2,8,1 und 4 in einen Heap einfügen. Sie können den Heap mit n Elementen aufbauen, indem Sie mit einem leeren Heap beginnen und ihn dann nacheinander mit O (nlogn) Zeit mit anderen Elementen füllen.

Heapify: Einfügealgorithmus, der beim Einfügen von Elementen in einen Heap hilft. Dabei wird geprüft, ob die Eigenschaft „Heap-Datenstruktur hervorgehoben“ ist.
Beispielsweise würde ein Max-Heapify prüfen, ob der Wert des übergeordneten Elements größer ist als der des untergeordneten Elements. Die Elemente können dann mit Methoden wie Swapping sortiert werden.

Zusammenführen: Wenn Sie davon ausgehen, dass Sie zwei Heaps zu einem zusammenfassen müssen, verwenden Sie Merge-Heaps, um die Werte der beiden Heaps zusammenzuführen. Die ursprünglichen Halden sind jedoch noch erhalten.

Inspizieren Sie Haufen

Beim Untersuchen von Heaps geht es darum, die Anzahl der Elemente in der Heap-Datenstruktur zu überprüfen und zu validieren, ob der Heap leer ist.

Es ist wichtig, Heaps beim Sortieren oder Einreihen von Elementen zu überprüfen. Es ist wichtig, mit Is-Empty() zu prüfen, ob Sie Elemente zum Verarbeiten haben. Die Heap-Größe hilft dabei, den Max-Heap oder Min-Heap zu finden. Sie müssen also die Elemente kennen, die der Heap-Eigenschaft folgen.

Größe – gibt die Größe oder Länge des Heaps zurück. Sie können erkennen, wie viele Elemente in sortierter Reihenfolge vorhanden sind.
Ist leer – Wenn der Heap NULL ist, wird TRUE zurückgegeben, andernfalls FALSE.

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 wirklichen Leben nützlich, wie zum Beispiel:

Hilft bei der Spam-Filterung.
Implementieren von Graphenalgorithmen.
OperaSystemlastausgleich und Datenkomprimierung.
Finden Sie die Reihenfolge in der Statistik.
Implementieren Sie Prioritätswarteschlangen, mit denen Sie in logarithmischer Zeit nach Elementen in einer Liste suchen können.
Heap-Datenstruktur wird auch zum Sortieren verwendet.
Simulation von Kunden an einer Leitung.
Behandlung unterbrechen Betriebssystem.
In Huffmans Codierung zur Datenkomprimierung.

Eigenschaften der Heap-Prioritätswarteschlange

Bei Prioritätsheaps werden die Datenelemente in der Liste miteinander verglichen, um das kleinere Element zu bestimmen.
Ein Element wird in eine Warteschlange gestellt und anschließend entfernt.
Jedes einzelne Element in der Prioritätswarteschlange verfügt über eine eindeutige Nummer, die als Priorität gekennzeichnet ist.
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

Heap-Sortierung in JAVA mit Codebeispiel

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 the root and the largest element 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 mit Codebeispiel

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)