Heap-datastruktur: Hva er Heap?

Hva er en heap-datastruktur?

En heap er en spesialisert trebasert datastruktur. Heap-datastrukturen består av en øverste node kalt roten (forelderen). Den andre noden er rotens venstre barn, mens den tredje noden er rotens høyre barn. De påfølgende nodene fylles fra venstre til høyre. Foreldre-node-nøkkelen sammenlignes med dens avkom, slik at et riktig arrangement oppstår. Treet er lett å visualisere der hver enhet kalles en node, og hver node har en unik nøkkel for identifikasjon.

Enkelt sagt er en Heap et komplett binært tre som tilfredsstiller heap-egenskapen: hver forelder er ordnet konsekvent mot sine barn, noe som gjør den ideell for prioritetskøer og Heap Sort.

Hvorfor trenger du Heap Data Structure?

Her er hovedgrunnene til å bruke en Heap:

• Heap-datastrukturen tillater sletting og innsetting i logaritmisk tid – O(log₂ikke).
• Dataene i treet er ordnet i en bestemt rekkefølge. I tillegg til å oppdatere eller spørre etter verdier som maksimum eller minimum, kan programmereren finne relasjoner mellom forelderen og avkommet.
• Du kan bruke konseptet Dokumentobjektmodell for å hjelpe deg med å forstå heap-datastrukturen visuelt.
• Heaps støtter effektive prioritetskøoperasjoner, som er kritiske for grafalgoritmer som Dijkstras korteste sti og Prims minimum spanning tree.

Typer av hauger

Heap Data Structure har forskjellige algoritmer for å håndtere innsettinger og fjerning av elementer, inkludert prioritetskø, binær heap, binomial heap og Sortering i bunke.

• Prioritetskø: Det er en magemuskeltract-datastruktur som inneholder prioriterte objekter. Hvert objekt eller element har en forhåndsbestemt prioritet. Derfor får objektet eller elementet som er tildelt høyest prioritet tjenesten før resten.
• Binær heap: Binære heaper er egnet for enkle heap-operasjoner som slettinger og innsettinger. De er standardimplementeringen bak de fleste standard bibliotekprioritetskøer.
• Binomialhaug: En binomialhaug består av en serie samlinger av binomialtrær som utgjør haugen. Et binomialhaugtre er ikke et vanlig tre, da det er strengt definert. Det totale antallet elementer i et binomialtre er alltid lik 2.ⁿ noder.
• Sortering i bunke: I motsetning til de fleste sorteringsalgoritmer bruker Heap Sort O(1)-plass for sorteringsoperasjonen sin. Det er en sammenligningsbasert sorteringsalgoritme der sortering skjer i stigende rekkefølge ved først å gjøre inputen om til en Max-Heap. Du kan se på Heap Sort som et oppgradert binært søketre.

Vanligvis bruker en heap-datastruktur to strategier. For input 12 – 8 – 4 – 2 og 1:

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

Min-haug

I Min-Heap-strukturen har rotnoden en verdi som enten er lik eller mindre enn nodens barn. Roten til en Min-Heap har derfor minimumsverdien. Min-Heapen er også et komplett binært tre.

Når du har en min-haug i et tre, er alle bladene levedyktige kandidater for maksimalverdien. Du må imidlertid undersøke hvert blad for å få den nøyaktige maks-haugverdien.

Eksempel på min-heap

I diagrammet ovenfor kan du se en tydelig sekvens fra roten til den laveste noden.

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

Max-Heap

I Max-Heap-strukturen har foreldre- eller rotnoden en verdi lik eller større enn de underordnede nodene. Denne noden har den maksimale verdien. Det er et komplett binært tre, slik at du kan bygge en Max-Heap fra en samling verdier i O(n) tid.

Her er noen metoder som vanligvis brukes når man implementerer en Java Maks-Heap:

• Legg til (): Plasserer et nytt element i en heap. Hvis du bruker en array, legges objektene til på slutten av arrayet, mens i binærtreet legges objektene til ovenfra og nedenfra og deretter fra venstre til høyre.
• Fjern (): Denne metoden lar deg fjerne det første elementet fra arraylisten. Siden det nylig forfremmede elementet ikke lenger er det største, skyver Sift-Down-metoden det alltid til sin nye plassering.
• Sil ned (): Denne metoden sammenligner et rotobjekt med dets barn og skyver deretter den flyttede noden til sin rettmessige posisjon.
• Sil opp (): Hvis du bruker array-metoden for å legge til et nylig innsatt element i en array, hjelper Sift-Up-metoden den nylig tillagte noden med å flytte seg til riktig posisjon. Det nye elementet sammenlignes først med det overordnede elementet ved å simulere tredatastrukturen.

  Bruk formelen Parent_Index = Child_Index / 2. Du fortsetter å gjøre dette til det største elementet er foran i tabellen.

Grunnleggende haug Operasjoner

For å finne de høyeste og laveste verdiene i et datasett, trenger du noen grunnleggende heap-operasjoner som finn, sett inn og slett. Fordi elementer stadig kommer og går, bør du vite hvordan 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 med nøkler, lager programmereren en tom heap og setter deretter inn de andre nøklene én om gangen ved hjelp av de grunnleggende heap-operasjonene.

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

• Heapify: En innsettingsrutine som hjelper med å sette inn elementer i en heap samtidig som heap-egenskapen bevares.

  For eksempel sjekker en max-heapify-operasjon at verdien til foreldreelementet er større enn avkommet. Elementene kan deretter sorteres ved hjelp av metoder som swap.ping.

• Slå sammen: Når du har to hauger som skal kombineres til én, bruker du merge-operasjonen for å bringe verdiene fra de to haugene sammen. De opprinnelige haugene bevares fortsatt.

Inspiser hauger

Inspeksjon av heaps refererer til å sjekke antall elementer i heap-datastrukturen og validere om heapen er tom.

Det er viktig å inspisere heaps mens man sorterer eller setter elementer i kø. Det er viktig å sjekke at det finnes elementer å behandle ved hjelp av Is-Empty(). Heapstørrelsen vil hjelpe med å finne Max-Heap- eller Min-Heap-røttene, så du må vite hvor mange elementer som følger heap-egenskapen.

• Størrelse – returnerer størrelsen eller lengden på haugen. Den forteller deg hvor mange elementer som er lagret i sortert rekkefølge.
• Er tom – returnerer SANN hvis heapen er null, ellers returneres USANN.

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, for eksempel:

• Hjelper med spamfiltrering.
• Implementering av grafalgoritmer som Dijkstra og Prim.
• Operalastbalansering og datakomprimering av systemet.
• Finne ordensstatistikk som det k-te minste elementet.
• Implementering av prioriterte køer der du kan søke etter elementer i en liste i logaritmisk tid.
• Heap-datastruktur brukes også til sortering gjennom Heap Sort.
• Simulering av kunder i kø.
• Avbryt håndtering i Operating System.
• I Huffman-koding for datakomprimering.
• Styrker best-først-søk og A*-heuristikker i AI-baneplanlegging.

Heap Priority Queue Properties

Følgende egenskaper beskriver hvordan prioritetskøen som er bygget på en heap oppfører seg:

• I prioritetshumper sammenlignes dataelementene i listen med hverandre for å bestemme det minste eller største elementet.
• Et element plasseres i en kø og fjernes deretter i prioritert rekkefølge.
• Hvert enkelt element i prioritetskøen har et unikt nummer knyttet til seg, identifisert som en prioritet.
• Når en prioritetskø forlates, forlates elementet med høyest prioritet først.

Fremgangsmåte for implementering av Heap Priority Queue i Java

Den neste seksjonen går over i betong Java implementering som gjør disse reglene om til fungerende kode.

Sorter i haug Java med Code Eksempel

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

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 Code Eksempel

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)

Produksjon

[1, 3, 4, 7, 9]

Deretter skal du lære om Biseksjonsmetode.

Spørsmål og svar