Heap-datastruktur: Hvad er en heap?

Hvad er en heap-datastruktur?

En heap er en specialiseret træbaseret datastruktur. Heap-datastrukturen består af en øverste node kaldet roden (forælder). Dens anden node er rodens venstre barn, mens den tredje node er rodens højre barn. De efterfølgende noder er udfyldt fra venstre mod højre. Forælder-nodenøglen sammenlignes med dens afkom, så der opstår en korrekt arrangement. Træet er let at visualisere, hvor hver enhed kaldes en node, og hver node har en unik nøgle til identifikation.

Enkelt sagt er en heap et komplet binært træ, der opfylder heap-egenskaben: hver forælder er ordnet konsistent i forhold til sine underordnede, hvilket gør den ideel til prioritetskøer og heapsortering.

Hvorfor har du brug for Heap Data Structure?

Her er de vigtigste grunde til at bruge en Heap:

• Heap-datastrukturen tillader sletning og indsættelse i logaritmisk tid – O(log₂ikke).
• Dataene i træet er arrangeret i en bestemt rækkefølge. Udover at opdatere eller forespørge på værdier så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 visuelt.
• Heaps understøtter effektive prioritetskøoperationer, som er kritiske for grafalgoritmer såsom Dijkstras korteste vej og Prims minimum spanning tree.

Typer af dynger

Heap Data Structure har forskellige algoritmer til håndtering af indsættelser og fjernelse af elementer, herunder Priority Queue, Binary Heap, Binomial Heap og Dynge sortering.

• Prioritetskø: Det er en mavemuskeltracen datastruktur, der indeholder prioriterede objekter. Hvert objekt eller element har en forudbestemt prioritet. Derfor får det objekt eller element, der har fået tildelt den højeste prioritet, tjenesten før resten.
• Binær bunke: Binære heaps er velegnede til simple heap-operationer såsom sletninger og indsættelser. De er standardimplementeringen bag de fleste standard biblioteksprioritetskøer.
• Binomial bunke: En binomial heap består af en række samlinger af binomialtræer, der udgør heapen. Et binomial heaptræ er ikke et almindeligt træ, da det er strengt defineret. Det samlede antal elementer i et binomialtræ er altid lig med 2.ⁿ noder.
• Sortering i bunke: 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 inputtet til en Max-Heap. Du kan se Heap Sort som et opgraderet binært søgetræ.

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

• Min-Heap – mindst værdi øverst
• Max-Heap – højeste værdi øverst

Min-Heap

I Min-Heap-strukturen har rodnoden en værdi, der enten er lig med eller mindre end nodens børn. Roden af ​​en Min-Heap har derfor minimumsværdien. Min-Heapen er også et komplet binært træ.

Når du har en Min-Heap i et træ, er alle bladene brugbare kandidater til den maksimale værdi. Du skal dog undersøge hvert blad for at få den nøjagtige Max-Heap-værdi.

Eksempel på min-heap

I diagrammet ovenfor kan du se en tydelig rækkefølge fra roden til den laveste knude.

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

Max-Heap

I Max-Heap-strukturen har den overordnede eller rodnode en værdi, der er lig med eller større end dens undernoder. Denne node indeholder den maksimale værdi. Det er et komplet binært træ, så du kan bygge en Max-Heap ud fra en samling af værdier i O(n) tid.

Her er et par metoder, der ofte bruges, når man implementerer en Java Max-Heap:

• Tilføj (): Placerer et nyt element i en heap. 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 fra venstre til højre.
• Fjern (): Denne metode giver dig mulighed for at fjerne det første element fra arraylisten. Da det nyligt forfremmede element ikke længere er det største, skubber Sift-Down-metoden det altid til sin nye placering.
• Sigt ned (): Denne metode sammenligner et rodobjekt med dets underobjekter og skubber derefter den flyttede node til sin rette 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 sig til sin korrekte position. Det nye element sammenlignes først med dets overordnede element ved at simulere træets datastruktur.

  Anvend formlen Parent_Index = Child_Index / 2. Du fortsætter med at gøre dette, indtil det maksimale element er forrest i arrayet.

Basic Heap Operationer

For at finde de højeste og laveste værdier i et datasæt, skal du bruge et par grundlæggende heap-operationer såsom find, insert og delete. Fordi elementer konstant kommer og går, bør du vide, hvordan 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 heaps er kendt som at oprette heaps. Givet en liste over nøgler opretter programmøren en tom heap og indsætter derefter de andre nøgler én ad gangen ved hjælp af de grundlæggende heap-operationer.

Så lad os begynde at bygge en Min-Heap ved hjælp af Williams metode ved at indsætte værdierne 12, 2, 8, 1 og 4. Du kan bygge heapen med n elementer ved at starte med en tom heap og derefter fylde den successivt med andre elementer ved hjælp af O(n log n) tid.

• Heapify: En indsættelsesrutine, der hjælper med at indsætte elementer i en heap, samtidig med at heap-egenskaben bevares.

  For eksempel kontrollerer en max-heapify-operation, at værdien af ​​​​forælderen er større end dens afkom. Elementerne kan derefter sorteres ved hjælp af metoder som swapping.

• Fusionere: Når du har to heaps, der skal kombineres til én, skal du bruge merge-operationen til at bringe værdierne fra de to heaps sammen. De oprindelige heaps bevares stadig.

Undersøg dynger

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

Det er vigtigt at inspicere heaps, når man sorterer eller sætter elementer i kø. Det er vigtigt at kontrollere, at der er elementer at behandle ved hjælp af Is-Empty(). Heapstørrelsen vil hjælpe med at finde Max-Heap- eller Min-Heap-rødderne, så du skal vide, hvor mange elementer der følger heap-egenskaben.

• Størrelse – returnerer størrelsen eller længden af ​​heapen. Den fortæller dig, hvor mange elementer der er gemt i sorteret rækkefølge.
• Er tom – returnerer TRUE, hvis heapen er null, ellers returneres FALSE.

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, såsom:

• Hjælper med spamfiltrering.
• Implementering af grafalgoritmer som Dijkstra og Prim.
• Operabelastningsbalancering og datakomprimering af systemet.
• At finde ordensstatistik, såsom det k-te mindste element.
• Implementering af prioriterede køer, hvor du kan søge efter elementer på en liste i logaritmisk tid.
• Heap-datastruktur bruges også til sortering via Heap Sort.
• Simulering af kunder i ventekø.
• Afbryd håndtering i Operating System.
• I Huffman-kodning til datakomprimering.
• Styrker bedst-først-søgning og A*-heuristikker i AI-stiplanlægning.

Egenskaber for bunkeprioriteret kø

Følgende egenskaber beskriver, hvordan prioritetskøen, der er bygget på en heap, opfører sig:

• I prioritetsheaps sammenlignes dataelementerne i listen med hinanden for at bestemme det mindste eller største element.
• Et element placeres i en kø og fjernes derefter i prioriteret rækkefølge.
• Hvert enkelt element i prioritetskøen har et unikt nummer relateret til det, der er identificeret som en prioritet.
• Når en prioritetskø forlades, afsluttes elementet med den højeste prioritet først.

Trin til implementering af Heap Priority Queue i Java

Den næste sektion bevæger sig ind i en beton Java implementering, der omdanner disse regler til fungerende kode.

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

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

Produktion

[1, 3, 4, 7, 9]

Dernæst vil du lære om Bisektionsmetode.

Ofte Stillede Spørgsmål