Heap-datastruktur: Hvad er Heap? Min & Max Heap (eksempel)

Hvad er en Heap?

Heap er en specialiseret trædatastruktur. Heapen omfatter den øverste knude kaldet en rod (forælder). Dens andet barn er rodens venstre barn, mens den tredje knude er rodens højre barn. De på hinanden følgende noder udfyldes fra venstre mod højre. Forældre-node-nøglen sammenligner med dens afkoms, og et ordentligt arrangement opstår. Træet er let at visualisere, hvor hver enhed kaldes en node. Noden har unikke nøgler til identifikation.

Hvorfor har du brug for Heap Data Structure?

Her er de vigtigste grunde til at bruge Heap Data Structure:

Heap-datastrukturen tillader sletning og indsættelse i logaritmisk tid – O(log₂ikke).
Dataene i træet er udformet i en bestemt rækkefølge. Udover at opdatere eller forespørge på ting som et maksimum eller minimum, kan programmøren finde relationer mellem forælderen og afkommet.
Du kan anvende begrebet Dokumentobjektmodel for at hjælpe dig med at forstå heap-datastrukturen.

Typer af dynger

Heap-datastruktur har forskellige algoritmer til håndtering af indsættelser og fjernelse af elementer i en heap-datastruktur, herunder Priority-Queue, Binary-Heap, Binomial Heap og Dynge-Sort.

Prioritetskø: Det er en abstrakt datastruktur, der indeholder prioriterede objekter. Hvert objekt eller element har en prioritet, der er forudbestemt for det. Derfor får det objekt eller element, der er tildelt højere prioritet, tjenesten før resten.
Binær-bunke: Binære heaps er velegnede til simple heap-operationer såsom sletninger og indsættelser.
Binomial-heap: En binomial bunke består af en række samlinger af binomiale træer, der udgør bunken. Binomial Heap-træ er ikke noget almindeligt træ, da det er strengt defineret. Det samlede antal elementer i et binomialtræ har altid 2ⁿ noder.
Heap-Sort: I modsætning til de fleste sorteringsalgoritmer bruger heap-sort O(1) plads til sin sorteringsoperation. Det er en sammenligningsbaseret sorteringsalgoritme, hvor sortering sker i stigende rækkefølge ved først at omdanne den til en max hob. Du kan se på en Heapsort som et opgraderet kvalitets binært søgetræ.

Typisk anvender en heap-datastruktur to strategier. Til input 12 – 8 – 4 – 2 og 1

Min bunke – mindst værdi i toppen
Max Heap – højeste værdi øverst

Min bunke

I Min Heap-strukturen har rodknuden en værdi, der enten er lig med eller mindre end børnene på den node. Denne heap node af en Min Heap har minimumsværdien. Alt i alt er dens min-heap struktur en komplet binært træ.

Når du først har en Min-bunke i et træ, er alle bladene levedygtige kandidater. Du skal dog undersøge hvert af bladene for at få den nøjagtige Max-heap-værdi.

Min bunke eksempel

I diagrammerne ovenfor kan du bemærke en klar sekvens fra roden til den laveste knude.

Antag, at du gemmer elementerne i Array Array_N[12,2,8,1,4]. Som du kan se fra arrayet, overtræder rodelementet Min Heap-prioriteten. For at vedligeholde Min-heap-egenskaben skal du udføre min-heapify-operationerne for at bytte elementerne, indtil Min-heap-egenskaberne er opfyldt.

Max Heap

I Max Heaps struktur har den overordnede eller rodnode en værdi, der er lig med eller større end dens børn i noden. Denne node har den maksimale værdi. Desuden er det et komplet binært træ, så du kan bygge en max heap ud fra en samling af værdier og køre den på O(n) tid.

Her er et par metoder til at implementere en java max heap

Tilføje (): anbring et nyt element i en bunke. Hvis du bruger et array, tilføjes objekterne i slutningen af arrayet, mens objekterne i det binære træ tilføjes fra top til bund og derefter efter venstre mod højre.
Fjern (): Denne metode giver dig mulighed for at fjerne det første element fra arraylisten. Da det nyligt tilføjede element ikke længere er det største, skubber Sift-Down-metoden det altid til dets nye placering.
Sigt ned (): Denne metode sammenligner et rodobjekt med dets underordnede objekt og skubber derefter den nyligt tilføjede node til sin retmæssige position.
Sigt op (): hvis du bruger array-metoden til at tilføje et nyligt indsat element til et array, hjælper Sift-Up-metoden den nyligt tilføjede node med at flytte til sin nye position. Det nyligt indsatte element sammenlignes først med det overordnede element ved at simulere trædatastrukturen.
Anvend formel Parent_Index=Child_Index/2. Du fortsætter med at gøre dette, indtil det maksimale element er foran i arrayet.

Basic Heap Operationer

For at du kan finde de højeste og laveste værdier i et sæt data, har du brug for masser af grundlæggende heap-operationer såsom find, slet og indsæt. Fordi elementer konstant vil komme og gå, skal du:

Finde – Se efter en genstand i en bunke.
indsatte – Tilføj et nyt barn i dyngen.
Slette – Slet en node fra en heap.

Opret dynger

Processen med at konstruere dynger er kendt som at skabe dynger. Med en liste over nøgler laver programmøren en tom bunke og indsætter derefter andre nøgler én ad gangen ved hjælp af grundlæggende heap-operationer.

Så lad os begynde at bygge en Min-heap ved at bruge Willaims metode ved at indsætte værdierne 12,2,8,1 og 4 i en heap. Du kan bygge bunken med n elementer ved at starte med en tom bunke og derefter fylde den successivt med andre elementer ved at bruge O (nlogn) tid.

Heapify: i indsættelsesalgoritme, som hjælper med at indsætte elementer i en heap. Kontroller, om ejendomsbunkens datastruktur er fremhævet, følges.
For eksempel ville en max heapify kontrollere, om værdien af forælderen er større end dens afkom. Elementerne kan derefter sorteres ved hjælp af metoder som at bytte.

Flet: I betragtning af at du har to dynger, der skal kombineres til én, skal du bruge Merge-dynger til at bringe værdierne fra de to dynger sammen. De originale dynger er dog stadig bevaret.

Undersøg dynger

Inspicering af heaps refererer til at kontrollere antallet af elementer i heap-datastrukturen og validere, om heapen er tom.

Det er vigtigt at inspicere dynger som sortering eller kø af elementer. Det er vigtigt at kontrollere, om du har elementer, der skal behandles ved hjælp af Is-Empty(). Hobestørrelsen hjælper med at lokalisere max-heapen eller min-heapen. Så du skal kende elementerne efter heap-egenskaben.

Størrelse – returnerer bunkens størrelse eller længde. Du kan se, hvor mange elementer der er i sorteret rækkefølge.
Er tom – hvis heapen er NULL, returnerer den TRUE ellers returnerer den FALSK.

Her udskriver du alle elementer i prioritet Q sløjfe og derefter kontrollere, at priorityQ ikke er tom.

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

Brug af heap-datastruktur

Heap datastruktur er nyttig i mange programmeringsapplikationer i det virkelige liv som:

Hjælper med spamfiltrering.
Implementering af grafalgoritmer.
Operasystembelastningsbalancering og datakomprimering.
Find rækkefølgen i statistikken.
Implementer prioritetskøer, hvor du kan søge efter elementer på en liste i logaritmisk tid.
Heap-datastruktur bruges også til sortering.
Simulering af kunder på en linje.
Afbryd håndteringen ind Operating System.
I Huffmans kodning til datakomprimering.

Egenskaber for bunkeprioriteret kø

I prioriterede dynger sammenlignes dataelementerne på listen med hinanden for at bestemme det mindre element.
Et element placeres i en kø og fjernes efterfølgende.
Hvert enkelt element i Prioritetskøen har et unikt nummer relateret til det identificeret som en prioritet.
Når du forlader en prioritetskø, afsluttes topprioritetselementet først.

Trin til implementering af heap Priority Queue i Java

Heap Sort i JAVA med kodeeksempel

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);
        }
    }
}

Produktion

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

Heap Sorter i Python med kodeeksempel

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)