Heap adatstruktúra: Mi az a kupac? Min és Max Heap (példa)

Mi az a kupac?

A kupac egy speciális fa adatstruktúra. A kupac tartalmazza a legfelső csomópontot, amelyet gyökérnek (szülőnek) neveznek. Második gyermeke a gyökér bal gyermeke, míg a harmadik csomópont a gyökér jobb gyermeke. Az egymást követő csomópontokat balról jobbra töltjük. A szülő-csomópont kulcsa összehasonlítható az utód kulcsával, és megfelelő elrendezés történik. A fa könnyen megjeleníthető, ahol minden entitást csomópontnak neveznek. A csomópont egyedi kulcsokkal rendelkezik az azonosításhoz.

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

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

A kupac adatstruktúra lehetővé teszi a törlést és beszúrást logaritmikus időben – O(log₂nem).
A fában lévő adatok meghatározott sorrendben vannak kialakítva. Az olyan dolgok frissítése vagy lekérdezése mellett, mint a maximum vagy minimum, a programozó kapcsolatokat találhat a szülő és az utód között.
Alkalmazhatja a koncepciót a Dokumentumobjektum-modell hogy segítsen megérteni a kupac adatszerkezetét.

A kupacok típusai

A kupac adatszerkezet különféle algoritmusokkal rendelkezik a beillesztések kezelésére és az elemek eltávolítására egy halom adatszerkezetben, beleértve a prioritás-sort, a bináris halom, a binomiális kupac és Heap-Sort.

Priority-Queue: Ez egy absztrakt adatstruktúra, amely prioritást élvező objektumokat tartalmaz. Minden objektumnak vagy elemnek előre meghatározott prioritása van. Ezért a magasabb prioritású objektum vagy elem előbb kapja meg a szolgáltatást, mint a többi.
Bináris halom: A bináris kupacok alkalmasak olyan egyszerű halomműveletekre, mint a törlés és beillesztés.
Binomiális kupac: A binomiális halom binomiális fák sorozatából áll, amelyek a kupacot alkotják. A binomiális kupacfa nem közönséges fa, mivel szigorúan meghatározott. Egy binomiális fa elemeinek teljes száma mindig 2ⁿ csomópontokat.
Halom szerinti rendezés: A legtöbb rendezési algoritmussal ellentétben a halom-rendezés 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 max kupacsá alakítva. A Heapsort-et egy továbbfejlesztett minőségű bináris keresési faként tekintheti meg.

A halom adatstruktúra általában két stratégiát alkalmaz. 12 – 8 – 4 – 2 és 1 bemenethez

Min Heap – a legkevesebb érték a tetején
Max Heap – a legmagasabb érték a tetején

Min Halom

A Min Heap struktúrában a gyökércsomópont értéke egyenlő vagy kisebb, mint az adott csomópont gyermekei. A Min Heap ezen kupaccsomópontja tartja a minimális értéket. Összességében a min-heap szerkezete teljes bináris fa.

Ha van egy Min halom egy fában, minden levél életképes jelölt. Mindazonáltal minden levelet meg kell vizsgálnia, hogy megkapja a pontos Max-halom értéket.

Minimális kupac példa

A fenti ábrákon világos sorrendet láthatunk a gyökértől a legalsó csomópontig.

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

Max Heap

A Max Heap szerkezetében a szülő vagy gyökércsomópont értéke egyenlő vagy nagyobb, mint a csomópontban lévő gyermekei. Ez a csomópont tartja a maximális értéket. Ráadásul ez egy teljes bináris fa, így maximum kupacot építhetsz értékek gyűjteményéből, és O(n) időn belül futtathatod.

Íme néhány módszer a java max kupac megvalósítására

Hozzáadás (): új elem elhelyezése egy kupacba. Ha tömböt használ, akkor az objektumok a tömb végére kerülnek hozzáadásra, míg a bináris fában az objektumok felülről lefelé, majd balról jobbra.
Eltávolítás (): Ez a módszer lehetővé teszi az első elem eltávolítását a tömblistából. Mivel az újonnan hozzáadott elem már nem a legnagyobb, a Sift-Down módszer mindig az új helyére tolja.
Leszitálás (): Ez a módszer összehasonlítja a gyökérobjektumot a gyermekével, majd az újonnan hozzáadott csomópontot a megfelelő pozícióba tolja.
Sift-Up (): ha a tömb módszerrel újonnan beillesztett elemet ad hozzá egy tömbhöz, akkor a Sift-Up metódus segít az újonnan hozzáadott csomópontnak az új pozícióba való áthelyezésében. Az újonnan beillesztett elemet először a szülővel hasonlítják össze a fa adatszerkezet szimulálásával.
Alkalmazza a Parent_Index=Child_Index/2 képletet. Ezt addig kell folytatni, amíg a maximális elem a tömb elejére nem kerül.

Alapkupac OperaTIONS

Ahhoz, hogy megtalálja a legmagasabb és legalacsonyabb értékeket egy adathalmazban, sok alapvető halomműveletre van szüksége, mint például a keresés, törlés és beszúrás. Mivel az elemek folyamatosan jönnek és mennek, a következőket kell tennie:

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 kupacok létrehozásának folyamatát kupacok létrehozásának nevezik. Adott egy kulcslistát, a programozó üres kupacot készít, majd az alapvető kupacműveletek segítségével egyesével beszúrja a többi kulcsot.

Kezdjük tehát a Min-halom felépítését Willaim módszerével úgy, hogy a 12,2,8,1, 4, XNUMX, XNUMX és XNUMX értékeket beillesztjük egy kupacba. A kupacot n elemből építheti fel úgy, hogy egy üres kupacból kezdi, majd O (nlogn) idővel egymás után tölti fel más elemekkel.

Heapify: beszúrási algoritmusban, amely segít elemeket beszúrni egy kupacba. Ellenőrzi, hogy a tulajdonsághalom adatszerkezet kiemelten van-e nyomva.
Például egy max heapify ellenőrzi, hogy a szülő értéke nagyobb-e, mint az utódja. Az elemek ezután rendezhetők olyan módszerekkel, mint például a csere.

Egyesítés: Tekintettel arra, hogy két kupacot kell egyesíteni, használjon egyesítő kupacokat a két kupac értékeinek egyesítéséhez. Az eredeti kupacok azonban továbbra is fennmaradtak.

Vizsgálja meg a kupacokat

A kupacok ellenőrzése a kupac adatszerkezetében lévő elemek számának ellenőrzésére és annak ellenőrzésére vonatkozik, hogy a kupac üres-e.

Fontos a halmok ellenőrzése, mint az elemek rendezése vagy sorba állítása. Fontos annak ellenőrzése, hogy vannak-e feldolgozandó elemei az Is-Empty() segítségével. A kupacméret segít megtalálni a maximális vagy minimális kupacot. Tehát ismernie kell a kupac tulajdonságot követő elemeket.

Méret – visszaadja a kupac nagyságát vagy hosszát. Megadhatja, hogy hány elem van rendezett sorrendben.
Üres – ha a kupac NULL, akkor IGAZ értéket ad vissza, ellenkező esetben FALSE-t ad vissza.

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 kupac adatstruktúra a való életben számos programozási alkalmazásban hasznos, például:

Segít a levélszemétszűrésben.
Gráfalgoritmusok megvalósítása.
Operarendszer terheléselosztása és adattömörítés.
Keresse meg a sorrendet a statisztikában.
Valósítsa meg a prioritási sorokat, ahol logaritmikus időben kereshet elemeket egy listában.
A halom adatstruktúrát a rendezéshez is használják.
Ügyfelek szimulálása egy vonalon.
A kezelés megszakítása Operating rendszer.
A Huffman-féle adattömörítési kódolásban.

Halom prioritási sor tulajdonságai

A prioritási kupacokban a lista adatelemeit összehasonlítják egymással a kisebb elem meghatározásához.
Egy elem sorba kerül, majd eltávolításra kerül.
A Priority Queue minden egyes eleméhez tartozik egy egyedi szám, amely prioritásként azonosítva van.
A prioritási sorból való kilépéskor a kiemelt prioritású elem lép ki először.

A kupac prioritási sor megvalósításának lépései Java

Halomrendezés JAVA-ban kódpéldával

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

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 kódpéldával

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)