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(log2nem).
- 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 2n 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öl – 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)
teljesítmény
[1, 3, 4, 7, 9]
Ezután megtudhatja Felezési módszer
Összegzésként
- A kupac egy speciális fa adatstruktúra. Képzeljünk el egy családfát szüleivel és gyermekeivel.
- A kupacok adatszerkezete Java lehetővé teszi a törlést és beszúrást logaritmikus időben – O(log2nem).
- Behalmozódik Python 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 kupacot, a binomiális kupacot és a halomrendezést.
- A Min Heap struktúrában a gyökércsomópont értéke egyenlő vagy kisebb, mint az adott csomópont gyermekei.
- A Max Heap szerkezetében a gyökércsomópont (szülő) értéke egyenlő vagy nagyobb, mint a csomópontban lévő gyermekei.
- 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.