Heap adatszerkezet: Mi a heap?

Mi az a halom adatszerkezet?

A heap egy speciális, fa alapú adatstruktúra. A heap adatstruktúra egy legfelső csomópontból, a gyökérből (szülőből) áll. A második csomópont a gyökér bal oldali gyermeke, míg a harmadik csomópont a gyökér jobb oldali gyermeke. Az egymást követő csomópontok balról jobbra töltődnek ki. A szülő-csomópont kulcs összehasonlítható az utód kulcsával, így megfelelő elrendezés jön létre. A fa könnyen vizualizálható, ahol minden entitást csomópontnak neveznek, és minden csomópontnak egyedi kulcsa van az azonosításhoz.

Egyszerűen fogalmazva, a Heap egy teljes bináris fa, amely kielégíti a heap tulajdonságot: minden szülő konzisztensen rendezett a gyermekeihez képest, ami ideálissá teszi prioritási sorokhoz és Heap rendezéshez.

Miért van szüksége a Heap adatszerkezetre?

Íme a Heap használatának fő okai:

• A Heap adatstruktúra logaritmikus idő alatt – O(log) – lehetővé teszi a törlést és a beszúrást.₂nem).
• A fában lévő adatok egy adott sorrendben vannak elrendezve. Az olyan értékek frissítése vagy lekérdezése mellett, mint a maximum vagy minimum, a programozó kapcsolatokat is kereshet a szülő és az utód között.
• Alkalmazhatja a koncepciót a Dokumentumobjektum-modell hogy segítsen vizuálisan megérteni a Heap adatszerkezetét.
• A halmok hatékony prioritási sorműveleteket támogatnak, amelyek kritikus fontosságúak olyan gráfalgoritmusok számára, mint a Dijkstra-féle legrövidebb út és a Prim-féle minimális feszítőfa.

A kupacok típusai

A Heap Data Structure különféle algoritmusokkal rendelkezik az elemek beszúrásának és eltávolításának kezelésére, beleértve a prioritási sort, a bináris halmot, a binomiális halmot és a Halom rendezés.

• Elsőbbségi sor: Ez egy hasizmottracPriorizált objektumokat tartalmazó adatstruktúra. Minden objektumhoz vagy elemhez előre beállított prioritás tartozik. Ezért a magasabb prioritású objektum vagy elem kapja meg a szolgáltatást a többi előtt.
• Bináris halom: A bináris heapek alkalmasak egyszerű heap műveletekhez, például törlésekhez és beszúrásokhoz. Ezek az alapértelmezett implementációk a legtöbb szabványos könyvtári prioritási sor mögött.
• Binomiális halom: Egy binomiális halom binomiális fák sorozatából áll, amelyek a halmot alkotják. A binomiális halomfa nem egy szokványos fa, mivel szigorúan definiált. A binomiális fa elemeinek teljes száma mindig 2.ⁿ csomópontokat.
• Halomrendezés: A legtöbb rendezőalgoritmussal ellentétben a Heap Sort O(1) teret használ a rendezési művelethez. Ez egy összehasonlításon alapuló rendezési algoritmus, ahol a rendezés növekvő sorrendben történik, először a bemenetet egy Max-Heap-pé alakítva. A Heap Sort-ot egy továbbfejlesztett bináris keresőfának tekinthetjük.

Egy halom adatstruktúra jellemzően két stratégiát alkalmaz. A 12 – 8 – 4 – 2 és 1 bemenetek esetén:

• Min-Heap – legalacsonyabb érték felül
• Max-Heap – legmagasabb érték felül

Min-Heap

A Min-Heap struktúrában a gyökércsomópont értéke vagy egyenlő, vagy kisebb, mint a csomópont gyermekeinek értéke. A Min-Heap gyökere tehát a minimális értéket tartalmazza. A Min-Heap egy teljes bináris fa is.

Ha egy fában létrehoztunk egy Min-Heap-et, akkor minden levél szóba jöhet a maximális érték elérésére. Azonban minden egyes levelet meg kell vizsgálnunk, hogy megkapjuk a pontos Max-Heap értéket.

Min-Heap példa

A fenti ábrán jól látható a gyökértől a legalacsonyabb csomópontig tartó sorrend.

Tegyük fel, hogy az elemeket az Array_N[12, 2, 8, 1, 4] tömbben tároljuk. Amint a tömbből látható, a gyökérelem megsérti a Min-Heap prioritást. A Min-Heap tulajdonság fenntartásához a min-heapify műveleteket kell végrehajtani az elemek felcseréléséhez, amíg a Min-Heap szabályok nem teljesülnek.

Max-Heap

A Max-Heap struktúrában a szülő- vagy gyökércsomópont értéke egyenlő vagy nagyobb, mint a gyermekeié. Ez a csomópont tartalmazza a maximális értéket. Ez egy teljes bináris fa, így egy Max-Heap struktúrát O(n) idő alatt felépíthetsz értékek egy gyűjteményéből.

Íme néhány módszer, amelyet általában a megvalósítás során használnak Java Max-Heap:

• Hozzáadás (): Új elemet helyez el egy halomban. Tömb használata esetén az objektumok a tömb végére kerülnek, míg a bináris fában az objektumok felülről lefelé, majd balról jobbra kerülnek hozzáadásra.
• Eltávolítás (): Ez a metódus lehetővé teszi az első elem eltávolítását a tömblistából. Mivel az újonnan előléptetett elem már nem a legnagyobb, a Sift-Down metódus mindig az új helyére helyezi át.
• Leszűrés (): Ez a metódus összehasonlítja a gyökérobjektumot a gyermekeivel, majd az áthelyezett csomópontot a megfelelő pozícióba helyezi.
• Szitálás (): Ha a tömb metódust használod egy újonnan beszúrt elem tömbhöz való hozzáadásához, akkor a Sift-Up metódus segít az újonnan hozzáadott csomópontnak a megfelelő pozícióba helyezni. Az új elemet először a szülőjével hasonlítja össze a fa adatstruktúra szimulációjával.

  Alkalmazd a Parent_Index = Child_Index / 2 képletet. Ezt addig folytasd, amíg a maximális elem a tömb elejére nem kerül.

Alapkupac OperaTIONS

Ahhoz, hogy megtaláld egy adathalmaz legmagasabb és legalacsonyabb értékét, néhány alapvető halomműveletre van szükséged, mint például a keresés, beszúrás és törlés. Mivel az elemek folyamatosan jönnek és mennek, tudnod kell, hogyan:

• Találjon – Keressen egy tárgyat egy kupacban.
• betétlap – Adjon hozzá egy új gyereket a kupachoz.
• Törölni – Csomópont törlése a kupacból.

Hozzon létre kupacokat

A heapek létrehozásának folyamatát heapek létrehozásának nevezzük. Adott kulcslista alapján a programozó létrehoz egy üres heap-et, majd az alapvető heap műveletek segítségével egyenként beszúrja a többi kulcsot.

Kezdjük el egy Min-Heap építését William módszerével a 12, 2, 8, 1 és 4 értékek beillesztésével. Az n elemű halmot úgy építhetjük fel, hogy egy üres halommal kezdünk, majd O(n log n) idő alatt egymás után más elemekkel töltjük fel.

• Heapify: Egy beszúrási rutin, amely segít elemeket beszúrni egy halomba, miközben megőrzi a halom tulajdonságot.

  Például egy max-heapify művelet ellenőrzi, hogy a szülő értéke nagyobb-e, mint az utód értéke. Az elemek ezután olyan metódusokkal rendezhetők, mint a swapping.

• Összeolvad: Ha két halom értékét kell egybevonni, az egyesítés művelettel egyesítheted a két halom értékeit. Az eredeti halmok továbbra is megőrződnek.

Vizsgálja meg a kupacokat

A heapek ellenőrzése a heap adatszerkezetében lévő elemek számának ellenőrzését és annak ellenőrzését jelenti, hogy a heap üres-e.

Fontos a heapek vizsgálata az elemek rendezése vagy sorba állítása közben. Fontos ellenőrizni, hogy vannak-e feldolgozandó elemek az Is-Empty() használatával. A heap mérete segít megtalálni a Max-Heap vagy Min-Heap gyökereit, ezért tudnod kell, hogy hány elem követi a heap tulajdonságot.

• Méret – visszaadja a halom nagyságát vagy hosszát. Megmutatja, hogy hány elem van rendezett sorrendben tárolva.
• Üres – IGAZ értéket ad vissza, ha a heap null, egyébként HAMIS értéket.

Itt az összes elemet kinyomtatja prioritásQ ciklust, majd ellenőrizze, hogy a priorityQ nem üres-e.

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

A kupac adatstruktúra felhasználása

A heap adatszerkezet számos programozási alkalmazásban hasznos a való életben, például:

• Segít a spam szűrésében.
• Gráfalgoritmusok, például Dijkstra és Prim megvalósítása.
• Operaa rendszer terheléselosztása és az adattömörítés.
• Rendezési statisztikák keresése, például a k-adik legkisebb elem.
• Prioritási sorok megvalósítása, ahol logaritmikus időben kereshetsz egy lista elemeit.
• A halom adatszerkezetet a halomrendezésen keresztüli rendezésre is használják.
• Várakozó sorban álló ügyfelek szimulálása.
• Megszakításkezelés a Operating rendszer.
• Huffman kódolás az adattömörítéshez.
• A legjobbat elsőként keresés és az A* heurisztikák támogatása a mesterséges intelligencia általi úttervezésben.

Halom prioritási sor tulajdonságai

A következő tulajdonságok leírják, hogyan viselkedik a halomra épített prioritási sor:

• A prioritási kupacokban a lista adatelemeit összehasonlítják egymással, hogy meghatározzák a kisebb vagy nagyobb elemet.
• Egy elemet egy sorba helyeznek, majd prioritási sorrendben eltávolítanak.
• A prioritási sorban minden egyes elemhez egyedi szám tartozik, amelyet prioritásként azonosítanak.
• Egy prioritási sorból való kilépéskor a legmagasabb prioritású elem lép ki először.

A Heap prioritási sor megvalósításának lépései a következőben: Java

A következő szakasz betonba kerül. Java olyan implementáció, amely ezeket a szabályokat működő kóddá alakítja.

Halom Rendezés Java ahol Code Példa

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

teljesítmény

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

Halom Rendezés Python ahol Code Példa

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)

teljesítmény

[1, 3, 4, 7, 9]

Ezután megismerkedhetsz a Felezési módszer.

GYIK