Heap-datastruktur: Hva er Heap? Min og maks haug (eksempel)

Hva er en haug?

Heap er en spesialisert tredatastruktur. Heapen omfatter den øverste noden kalt en rot (foreldre). Det andre barnet er rotens venstre barn, mens den tredje noden er rotens høyre barn. De påfølgende nodene fylles fra venstre mot høyre. Foreldre-node-nøkkelen sammenlignes med den til avkommet, og en riktig ordning oppstår. Treet er lett å visualisere hvor hver enhet kalles en node. Noden har unike nøkler for identifikasjon.

Hvorfor trenger du Heap Data Structure?

Her er hovedgrunnene til å bruke Heap Data Structure:

Heap-datastrukturen tillater sletting og innsetting i logaritmisk tid – O(log₂ikke).
Dataene i treet er utformet i en bestemt rekkefølge. I tillegg til å oppdatere eller spørre etter ting som maksimum eller minimum, kan programmereren finne forhold mellom foreldrene og avkommet.
Du kan bruke konseptet Dokumentobjektmodell for å hjelpe deg med å forstå haugdatastrukturen.

Typer av hauger

Heap-datastruktur har forskjellige algoritmer for håndtering av innsettinger og fjerning av elementer i en heap-datastruktur, inkludert Priority-Queue, Binary-Heap, Binomial Heap og Heap-Sort.

Prioritetskø: Det er en abstrakt datastruktur som inneholder prioriterte objekter. Hvert objekt eller element har en forhåndsdefinert prioritet for det. Derfor får objektet eller elementet som er tildelt høyere prioritet tjenesten før resten.
Binær-haug: Binære hauger er egnet for enkle haugoperasjoner som slettinger og innsettinger.
Binomial-haug: En binomial haug består av en serie samlinger av binomiale trær som utgjør haugen. Binomial Heap-tre er ikke noe vanlig tre da det er strengt definert. Det totale antallet elementer i et binomialtre har alltid 2ⁿ noder.
Heap-Sort: I motsetning til de fleste sorteringsalgoritmer, bruker heap-sort O(1)-plass for sorteringsoperasjonen. Det er en sammenligningsbasert sorteringsalgoritme der sortering skjer i økende rekkefølge ved først å gjøre den om til en maksimal haug. Du kan se på en Heapsort som et oppgradert kvalitets binært søketre.

Vanligvis bruker en haugdatastruktur to strategier. For inngang 12 – 8 – 4 – 2 og 1

Min haug – minst verdi på toppen
Max Heap – høyeste verdi øverst

Min haug

I Min Heap-strukturen har rotnoden en verdi enten lik eller mindre enn barna på den noden. Denne heap-noden til en Min Heap har minimumsverdien. Alt i alt er min-heap-strukturen komplett binært tre.

Når du har en Min-haug i et tre, er alle bladene levedyktige kandidater. Du må imidlertid undersøke hvert av bladene for å få den nøyaktige Max-heap-verdien.

Min haug eksempel

I diagrammene ovenfor kan du legge merke til en klar sekvens fra roten til den laveste noden.

Anta at du lagrer elementene i Array Array_N[12,2,8,1,4]. Som du kan se fra matrisen, bryter rotelementet Min Heap-prioriteten. For å opprettholde Min-heap-egenskapen, må du utføre min-heapify-operasjonene for å bytte elementene til Min-heap-egenskapene er oppfylt.

Max Heap

I Max Heaps struktur har den overordnede eller rotnoden en verdi som er lik eller større enn dens underordnede i noden. Denne noden har maksimumsverdien. Dessuten er det et komplett binært tre, så du kan bygge en maksimal haug fra en samling verdier og kjøre den på O(n)-tid.

Her er noen få metoder for å implementere en java max-haug

Legg til (): plasser et nytt element i en haug. Hvis du bruker en matrise, legges objektene til på slutten av matrisen, mens i det binære treet legges objektene til fra topp til bunn og deretter etter venstre mot høyre.
Fjern (): Denne metoden lar deg fjerne det første elementet fra matriselisten. Siden det nylig lagt til elementet ikke lenger er det største, skyver Sift-Down-metoden det alltid til sin nye plassering.
Sile ned (): Denne metoden sammenligner et rotobjekt med dets underordnede objekt og skyver deretter den nylig lagt til noden til sin rettmessige posisjon.
Sil opp (): hvis du bruker array-metoden til å legge til et nylig innsatt element i en array, hjelper Sift-Up-metoden den nylig lagt til noden med å flytte til sin nye posisjon. Det nylig innsatte elementet sammenlignes først med det overordnede ved å simulere tredatastrukturen.
Bruk formelen Parent_Index=Child_Index/2. Du fortsetter å gjøre dette til det maksimale elementet er foran i arrayet.

Grunnleggende haug Operasjoner

For at du skal finne de høyeste og laveste verdiene i et sett med data, trenger du mange grunnleggende heap-operasjoner som å finne, slette og sette inn. Fordi elementer hele tiden kommer og går, må du:

Finn – Se etter en gjenstand i en haug.
innfelt – Legg til et nytt barn i haugen.
Delete – Slett en node fra en haug.

Lag hauger

Prosessen med å konstruere hauger er kjent som å lage hauger. Gitt en liste over nøkler, lager programmereren en tom haug og setter deretter inn andre nøkler en om gangen ved å bruke grunnleggende haugoperasjoner.

Så la oss begynne å bygge en Min-heap ved å bruke Willaims metode ved å sette inn verdiene 12,2,8,1 og 4 i en haug. Du kan bygge haugen med n elementer ved å starte med en tom haug og deretter fylle den suksessivt med andre elementer ved å bruke O (nlogn) tid.

Heapify: i innsettingsalgoritme, som hjelper til med å sette inn elementer i en haug. Kontroller, om egenskapshaugens datastruktur er uthevet, følges.
For eksempel vil en maks heapify sjekke om verdien til forelderen er større enn dens avkom. Elementene kan deretter sorteres ved hjelp av metoder som å bytte.

Slå sammen: Med tanke på at du har to hauger å kombinere til én, bruk flettehauger for å bringe verdiene fra de to haugene sammen. Imidlertid er de opprinnelige haugene fortsatt bevart.

Inspiser hauger

Inspeksjon av hauger refererer til å sjekke antall elementer i haugdatastrukturen og validere om haugen er tom.

Det er viktig å inspisere hauger som sortering eller kø av elementer. Det er viktig å sjekke om du har elementer å behandle ved å bruke Is-Empty(). Bunnstørrelsen hjelper deg med å finne maks-haugen eller min-heapen. Så du må kjenne til elementene etter heap-egenskapen.

Størrelse – returnerer størrelsen eller lengden på haugen. Du kan se hvor mange elementer som er i sortert rekkefølge.
Er-tom – hvis heapen er NULL, returnerer den TRUE ellers returnerer den FALSE.

Her skriver du ut alle elementene i prioritet Q løkke og deretter sjekke at priorityQ ikke er tom.

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

Bruk av haugdatastruktur

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

Hjelper med spamfiltrering.
Implementering av grafalgoritmer.
Operating Systembelastningsbalansering og datakomprimering.
Finn rekkefølgen i statistikken.
Implementer Prioritetskøer der du kan søke etter elementer i en liste i logaritmisk tid.
Heap datastruktur brukes også til sortering.
Simulering av kunder på en linje.
Avbryt håndteringen inn Operating System.
I Huffmans koding for datakomprimering.

Heap Priority Queue Properties

I prioriterte hauger blir dataelementene i listen sammenlignet med hverandre for å bestemme det mindre elementet.
Et element plasseres i en kø og fjernes deretter.
Hvert enkelt element i Prioritetskøen har et unikt nummer knyttet til det identifisert som en prioritet.
Når du går ut av en prioritetskø, avsluttes det øverste prioritetselementet først.

Trinn for å implementere heap Priority Queue i Java

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

Produksjon

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

Sorter i haug 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)