Heap-datastruktur: Vad är Heap? Min & Max Heap (exempel)

Vad är en heap?

Heap är en specialiserad träddatastruktur. Högen består av den översta noden som kallas en rot (förälder). Dess andra barn är rotens vänstra barn, medan den tredje noden är rotens högra barn. De på varandra följande noderna fylls från vänster till höger. Föräldernodnyckeln jämförs med dess avkomma, och ett korrekt arrangemang inträffar. Trädet är lätt att visualisera där varje entitet kallas en nod. Noden har unika nycklar för identifiering.

Varför behöver du Heap Data Structure?

Här är de främsta anledningarna till att använda Heap Data Structure:

Högdatastrukturen tillåter radering och infogning i logaritmisk tid – O(log₂inte).
Data i trädet utformas i en viss ordning. Förutom att uppdatera eller fråga saker som ett maximum eller minimum, kan programmeraren hitta relationer mellan föräldern och avkomman.
Du kan tillämpa begreppet Dokumentobjektmodell för att hjälpa dig att förstå högdatastrukturen.

Typer av högar

Heap-datastruktur har olika algoritmer för att hantera insättningar och ta bort element i en heap-datastruktur, inklusive Priority-Queue, Binary-Heap, Binomial Heap och Hög-Sortera.

Prioritetskö: Det är en abstrakt datastruktur som innehåller prioriterade objekt. Varje objekt eller föremål har en prioritet förberedd för det. Därför får objektet eller objektet som tilldelas högre prioritet tjänsten före resten.
Binär-hög: Binära heaps är lämpliga för enkla heap-operationer som raderingar och infogningar.
Binomial-Heap: En binomialhög består av en serie samlingar av binomialträd som utgör högen. Binomial Heap-träd är inget vanligt träd eftersom det är strikt definierat. Det totala antalet element i ett binomialträd har alltid 2ⁿ knutpunkter.
Heap-Sort: Till skillnad från de flesta sorteringsalgoritmer använder heap-sort O(1)-utrymme för sin sorteringsoperation. Det är en jämförelsebaserad sorteringsalgoritm där sortering sker i ökande ordning genom att först omvandla den till en maxhög. Du kan se en Heapsort som ett uppgraderat binärt sökträd av hög kvalitet.

Vanligtvis använder en högdatastruktur två strategier. För ingång 12 – 8 – 4 – 2 och 1

Min Heap – minsta värde överst
Max Heap – högsta värdet överst

Min hög

I Min Heap-strukturen har rotnoden ett värde som antingen är lika med eller mindre än barnen på den noden. Denna heapnod av en Min Heap har minimivärdet. Sammantaget är dess min-heap-struktur en komplett binärt träd.

När du väl har en Min-hög i ett träd är alla löv livskraftiga kandidater. Du måste dock undersöka vart och ett av bladen för att få det exakta Max-heap-värdet.

Min Heap Exempel

I diagrammen ovan kan du märka en tydlig sekvens från roten till den lägsta noden.

Anta att du lagrar elementen i Array Array_N[12,2,8,1,4]. Som du kan se från arrayen bryter rotelementet mot Min Heap-prioriteten. För att behålla egenskapen Min heap måste du utföra min-heapify-operationerna för att byta elementen tills Min-heap-egenskaperna uppfylls.

Max Heap

I Max Heaps struktur har den överordnade eller rotnoden ett värde lika med eller större än dess underordnade i noden. Denna nod har maxvärdet. Dessutom är det ett komplett binärt träd, så du kan bygga en maxhög från en samling värden och köra den på O(n)-tid.

Här är några metoder för att implementera en java max-hög

Lägg till (): placera ett nytt element i en hög. Om du använder en array läggs objekten till i slutet av arrayen, medan i det binära trädet läggs objekten till uppifrån och ner och sedan efter vänster till höger.
Avlägsna (): Denna metod låter dig ta bort det första elementet från arraylistan. Eftersom det nyligen tillagda elementet inte längre är det största, skjuter Sift-Down-metoden alltid det till sin nya plats.
Sålla ner (): Denna metod jämför ett rotobjekt med dess underordnade och skjuter sedan den nyligen tillagda noden till dess rättmätiga position.
Sålla upp (): om du använder arraymetoden för att lägga till ett nyligen infogat element i en array, så hjälper Sift-Up-metoden den nyligen tillagda noden att flytta till sin nya position. Det nyligen infogade objektet jämförs först med det överordnade genom att simulera träddatastrukturen.
Använd formeln Parent_Index=Child_Index/2. Du fortsätter att göra detta tills det maximala elementet är längst fram i arrayen.

Basic Heap Operationer

För att du ska hitta de högsta och lägsta värdena i en datauppsättning behöver du massor av grundläggande heap-operationer som hitta, ta bort och infoga. Eftersom element ständigt kommer och går måste du:

hitta – Leta efter ett föremål i en hög.
Insert – Lägg till ett nytt barn i högen.
Radera – Ta bort en nod från en hög.

Skapa högar

Processen att konstruera högar är känd som att skapa högar. Med en lista med nycklar gör programmeraren en tom hög och sätter sedan in andra nycklar en i taget med hjälp av grundläggande heap-operationer.

Så låt oss börja bygga en Min-hög med Willaims metod genom att infoga värdena 12,2,8,1 och 4 i en hög. Du kan bygga högen med n element genom att börja med en tom hög och sedan fylla den successivt med andra element med O (nlogn) tid.

Heapify: i insättningsalgoritm, som hjälper till att infoga element i en hög. Kontroller, om egenskapshögens datastruktur är markerad, följs.
Till exempel skulle en max heapify kontrollera om värdet på föräldern är större än dess avkomma. Elementen kan sedan sorteras med metoder som att byta.

Sammanfoga: Med tanke på att du har två högar att kombinera till en, använd merge heaps för att sammanföra värdena från de två högarna. De ursprungliga högarna är dock fortfarande bevarade.

Inspektera Heaps

Inspektera heaps hänvisar till att kontrollera antalet element i heapdatastrukturen och validera om heapen är tom.

Det är viktigt att inspektera högar som sortering eller köning av element. Att kontrollera om du har element att bearbeta med hjälp av Is-Empty() är viktigt. Högstorleken hjälper till att lokalisera max-högen eller min-högen. Så du måste känna till elementen efter heap-egenskapen.

Storlek – returnerar högens storlek eller längd. Du kan se hur många element som är i sorterad ordning.
Är tom – om högen är NULL returnerar den TRUE annars returnerar den FALSE.

Här skriver du ut alla element i prioritetQ loop och kontrollera sedan att priorityQ inte är tom.

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

Användningar av Heap Data Structure

Högdatastruktur är användbar i många programmeringsapplikationer i verkligheten som:

Hjälper till med skräppostfiltrering.
Implementering av grafalgoritmer.
Operasystembelastningsbalansering och datakomprimering.
Hitta ordningen i statistiken.
Implementera Prioritetsköer där du kan söka efter objekt i en lista i logaritmisk tid.
Högdatastruktur används också för sortering.
Simulera kunder på en linje.
Avbryt hanteringen in Operating System.
I Huffmans kodning för datakomprimering.

Högprioriterade köegenskaper

I prioriterade högar jämförs dataposterna i listan med varandra för att bestämma det mindre elementet.
Ett element placeras i en kö och tas sedan bort.
Varje enskilt element i Priority Queue har ett unikt nummer relaterat till sig identifierat som en prioritet.
När du lämnar en prioritetskö avslutas det högsta prioritetselementet först.

Steg för att implementera heap Priority Queue i Java

Högsortering i JAVA med kodexempel

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

Hög sortera in Python med kodexempel

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)