Max Heap Java nyelven

A bináris fa

A Java-ban sokféle adatstruktúra létezik. A kupac egy bináris fának nevezett fastruktúrán alapul . A bináris fa csomópontokból áll, amelyek mindegyikének legfeljebb 2 gyermekcsomópontja lehet: A bináris fa egy szülőcsomópontból áll, amelynek 0-2 csomópontja lehet. Lehet benne bal oldali gyermek csomópont és/vagy jobb oldali gyermek csomópont, vagy egyáltalán nem. Egy teljes bináris fában az összes csomópont ki van töltve, kivéve az utolsó szintet, amely lehet tele, de nem kell tele lennie. Az utolsó, az n-edik szint 1-2n csomópontot tartalmazhat, ahol az első n = 0-nál van, és a gyökér.

Max Heap

A Max heap (vagy maxheap) egy teljes bináris fa . A lényeg az, hogy a szülőcsomópontnak nagyobb vagy egyenlő értékkel kell rendelkeznie, mint a bal és a jobb oldali gyermek csomópont értéke. Ha ezt nem tartják be, akkor nincs max kupacod. Ezzel szemben a min kupac ennek az ellenkezője, ahol a gyökér a legkisebb érték, és az egymást követő csomópontok értéke nő; minden gyermek csomópont értéke nagyobb vagy egyenlő, mint a szülője. Ez is egy teljes bináris fa. Példa a max kupacra: Max kupac építhető tömbből. Ezt a tömböt faként fogjuk felfogni. Egy kupac esetében, ha a gyökér (a fa legfelső szülőcsomópontja) az n pozícióban (index) van tárolva, akkor a tömbhöz, a tömbhöz, mint Tömb [n] van megadva.. A bal és a jobb oldali gyermekcsomópont tehát a Tömb[2n+1] , illetve a Tömb[2n+2] pontban található. A max kupac esetén a gyökér a theArray[0] helyen van . Az n szintnél az n gyökér = 0: azArr[n] a szülőcsomópont az Arr[(2*n)+1] a bal oldali gyermekcsomópont az Arr[(2*n)+2] a jobb gyermekcsomópont

A PriorityQueue osztály

A Java kupacok a PriorityQueue osztály használatával valósíthatók meg . A PriorityQueues a gyűjtemény legfontosabb vagy legkevésbé fontos elemeinek megtalálására szolgál. A PriorityQueue osztály a java.util.package fájlban található . A PriorityQueues-t olyan objektumokból kell kialakítani, amelyek összehasonlíthatók, hogy meghatározott sorrendbe kerüljenek a sorban. A PriorityQueue-nek lehet egy összehasonlítója, így az objektumok összehasonlítása és a sor ennek az összehasonlításnak megfelelően jön létre. Példa erre:

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main
{
    public static void main(String[] args) {
        // Create PriorityQueue with comparator for ascending order of array length
        PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
        Integer [] array1 = {1, 2, 4, 6, 8, 9};
        Integer [] array2 = {3, 6, 9};
        Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
        Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
        Integer [] array5 = {4};

        //Add the array lengths to intQueue
        intQueue.add(array1.length);
        intQueue.add(array2.length);
        intQueue.add(array3.length);
        intQueue.add(array4.length);
        intQueue.add(array5.length);
        //Write out contents of intQueue as stored
        while (intQueue.size() != 0) {
            System.out.println(intQueue.remove());
        }
    }
}

Kimenet adása: Ebben a példában az intQueue alapértelmezett mérete 11, ezért nincs megadva (általában az első argumentum a komparátor előtt), és a komparátor a következőképpen van megadva: Ez összehasonlítja az intQueue- ben lévő elemeket , és növekvő sorrendben rendezi őket tömbhosszúságokba.

A PriorityQueue megvalósítása maximális kupac létrehozásához

A PriorityQueue osztály alapértelmezés szerint min kupac, összehasonlító nélkül. A min kupac a max kupac ellentéte, így a gyökér a legkisebb érték, és az egymást követő gyermekcsomópontok nagyobbak vagy egyenlőek a gyökérrel és az azt követő szülői csomópontokkal. Emiatt a max heap esetén a Java Collections keretrendszeréből származó reverseOrder() függvényt kell használni összehasonlítóként. Ez biztosítja, hogy max kupacot kapjunk, és nem minimális kupacot. Ez az osztály olyan hasznos metódusokkal rendelkezik, mint az add() , include() , remove() , poll() és peek() . Az elemek hozzáadódnak a sorhoz, és tetszőleges sorrendben lehetnek. Az új PriorityQueue várólista ezeket az elemeket maximális kupacként, fordított sorrendben tárolja. A sor kiírásakor a sorrend a következő lesz: Gyökér Bal-gyerek gyökérrel szülőként (Bal-gyermek_1) Jobb-gyermek, gyökérrel szülőként (Right-child_1) Bal-gyermek, Bal-gyermek_1 szülőként (Bal-gyermek_2 ) Jobb-gyerek Bal-gyermek_1-vel szülőként (Jobb-gyermek_2) Bal-gyerek jobb-gyermek_1-vel szülőként (Bal-gyermek_3) Jobb-gyermek jobb-gyermek_1-vel szülőként (Jobb-gyermek_3) Bal-gyerek Bal-gyermek_2-vel mint szülő (Left-child_4) Jobb-gyermek, Left-child_2 mint szülő (Right-child_4), stbA következő kód egy példa arra, hogyan jön létre a max kupac (maxheap) java-ban. Első lépésként egy tömböt kell kitölteni azokkal az értékekkel, amelyekhez a max kupac létrejön. Ezt tömbnek hívják . Ezután létrejön egy PriorityQueue , theQueue , majd ehhez adjuk hozzá az Array elemeit. Ez az add() metódust használja , pl. theQueue.add(10) 10 hozzáadásához a sor végéhez. A PriorityQueue osztály néhány funkciójának szemléltetésére a peek() metódus segítségével keressük meg a kupac fejét, és ez a maximális érték, jelen esetben 99. A következő feladat a kupac méretének ellenőrzése. a size() használatávalamelyről kiderül, hogy 9, és ezt kinyomtatják a konzolra. Módszer writeMaxHeap kiírja a sorban lévő elemeket gyökér sorrendben, bal-gyermek a gyökérrel szülőként, jobb-gyermek a gyökérrel szülőként, bal-gyermek első bal-gyermekkel szülőként, jobb-gyermek az első bal-gyermekkel mint szülő, jobb-gyermek első jobb-gyermek szülőként, bal-gyerek első jobb-gyermek szülőként stb., a következő értékekkel a bal és a jobb oldali gyermekek szülőként a fenti sorrendben. A PriorityQueue metódus tartalmazza(J) arra szolgál, hogy megtudja, hogy egy adott elem, J, benne van-e a sorban. Ebben az esetben J = 10-et keresünk. Példánkban igaz, hogy ez benne van a sorban, így ez igazként kerül kiírásra a konzolba. Egy másik PriorityQueue metódus, a remove(J) ezután a J = 10 eltávolítására szolgál a Queue- ból . A PriorityQueue funkcióinak részletesebb bemutatása érdekében a poll() metódus a head elem (maximális érték) eltávolítására szolgál egy while ciklus segítségével, minden alkalommal eltávolítva a head elemet az új sorból, és minden alkalommal eggyel csökkentve a sor méretét. Ez a writeQueue metódusban történikfőről hívják. Minden eltávolított elem kinyomtatása a konzolra kerül. Az eredeti sorban végül nem maradnak elemek. A nyomtatott elemek a max kupac érték szerinti csökkenő sorrendben, ahol minden alkalommal a sor feje kerül kinyomtatásra.

mport java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeap {

       public static void writeQueue(PriorityQueue<Integer> priorityQueue)
       {
           // Write out elements in queue, priorityQueue, and remove them using poll()
           while(priorityQueue.size() != 0)
           {
               System.out.println(priorityQueue.poll());
           }
       }

       public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
       {
           // Write out elements in queue as a max heap - root, left child, right child, etc
           for (Integer element : priorityQueue) {
               System.out.println(element);
           }
       }

       public static void main(String args[])
       {
           // Array of numbers to create a max heap array from
           int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};

           // theQueue is created
           PriorityQueue<Integer> theQueue =
                   new PriorityQueue<Integer>(Collections.reverseOrder());

           // Elements are added to theQueue
           for (int i = 0 ; i <theArray.length; ++i)
           {
               theQueue.add(theArray[i]);
           }

           // The head or root element (priority element) is printed out
           System.out.println("The root value is : " +  theQueue.peek());

           // Find size of theQueue. Use method size()
           Integer s = theQueue.size();
           System.out.println("Size of theQueue? " + s);

           // All elements of theQueue are printed in terms of parent,
           // left child, right child
           System.out.println("theQueue written using for loop:");
           writeMaxHeap(theQueue);

           // Does theQueue contain 10? Use method contains()
           boolean b = theQueue.contains(10);
           System.out.println("Does theQueue contain 10? " + b);

           // Erasing value 10 from array using remove()
           theQueue.remove(10);

           // All elements of theQueue are printed out and removed.
           // Each one is the maximum value left in the queue.
           // At the end theQueue will be empty
           System.out.println("theQueue written out using poll():");
           writeQueue(theQueue);

           // Find size of theQueue. Use method size()
           s = theQueue.size();
           System.out.println("Size of theQueue? " + s);
       }
   }

Kimenet:

Max Heapify

A Max Heapify algoritmust arra használjuk, hogy biztosítsuk, hogy egy bináris fa maximális kupac legyen. Ha egy csomópontnál vagyunk, az n és a gyermek csomópontok, a bal és a jobb is max kupacok, akkor remek, van egy max kupacunk. Ha ez nem így van az egész fában, akkor nincs max kupacunk. A Max Heapify algoritmus a fa rendezésére szolgál, hogy az megfeleljen a maxheap elveknek. A Max Heapify csak egy csomóponton működik. Ha az a követelmény, hogy a tömb max. kupac tömb legyen, akkor az összes alfát a gyökér előtt maxheap-re kell konvertálni, egyenként. Az algoritmust minden csomóponton alkalmazni kell. Ez N/2 csomóponton történik (a levelek megfelelnek a maximális kupac követelményeknek). A kupac időbonyolultsága O(NlogN), egy X magasságú csomópont esetén pedig O(X). A következő kód megmutatja, hogyan lehet maximalizálni egy fát (tömböt).

public class MaxHeapify

{
   public static Integer[] maxHeapify(Integer[ ] array, Integer i)
   {
       // Create left-child and right-child for the node in question
       Integer leftChild = 2 * i + 1;
       Integer rightChild = 2 * i + 2;

       // Assign maxVal to parent node, i
       Integer maxVal = i;

       // Set maxVal to greater of the two: node or left-child
       if( leftChild < array.length && array[leftChild] > array[maxVal] )
           maxVal = leftChild;

       // Set maxVal to greater of the two: maxVal or right-child
       if( rightChild < array.length && array[rightChild] > array[maxVal] )
           maxVal = rightChild;

       // Check if maxVal is not equal to parent node, then set parent node to
       // maxVal, swap values and then do a maxheapify on maxVal
       // which is now the previous parent node
       if( maxVal != i )
       {
           Integer value = array[i];
           array[i] = array[maxVal];
           array[maxVal] = value;
           array = maxHeapify(array, maxVal);
       }

       return array;
   }


   public static Integer[] maxHeapCreate(Integer array[])
   {
       // Call maxHeapify to arrange array in a max heap
       Integer [] theNewArr = array;
       for( Integer i = array.length/2; i >= 0; i-- )
           theNewArr = maxHeapify(array, i);

       return theNewArr;
   }

   public static void main(String[] args)
   {
       // Create array to be maxheapified, theArray,
       // and array, newArray, to write results into, by calling maxheapCreate
       // newArray will now be a maxheap
       Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
       Integer[ ] newArray = maxHeapCreate(theArray);

       // Print out contents of newArray
       System.out.println("newArray:");
       for(int i = 0; i < newArray.length; ++i)
       {
           System.out.println(newArray[i]);
       }

       // Print out labelled contents of newArray
       System.out.println(" root : " + newArray[0]);
       for (int i = 0; i <= newArray.length/2 - 1; i++) {
           System.out.print(" parent node : " + newArray[i] + " left child : " +
                            newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
           System.out.println();
       }
  }
}

Kimenet adása: Ebben a kódban a tömb jön létre, és számokkal van kitöltve. Létrejön egy második tömb, a newArray , amely ezúttal a maxheapCreate metódus eredményét fogja tartalmazni , a max kupactömböt. A maxHeapCreate metódus meghívása a main -ból történik , és itt egy új tömb, a theNewArr jön létre, és kitöltődik a maxHeapify eredményekkel. Ez úgy történik, hogy a bemeneti tömb méretének több mint felét hurkolja. A ciklus minden egyes lépésénél a maxHeapify metódus meghívása a tömb közepén lévő elemtől kezdődik és az elsővel végződik. A maxHeapify minden egyes hívásához, a szülőcsomópont bal és jobb gyermeke, i, megkeresésre kerül, és ellenőrzik, hogy melyik a legnagyobb a három közül, ezt maxValként határozva meg . Ha a maxVal nem egyenlő a szülőcsomóponttal, akkor csere történik, így a szülőcsomópont és a maxVal felcserélődik, majd a maxHeapify ezúttal is meghívásra kerül a maxVal- on , és ugyanazokat a lépéseket hajtja végre, mint korábban. Végül létrejön a maximális kupac, és nem kell több iterációt végrehajtani. A frissített tömb, a tömb , most newArray néven kerül vissza a főbe , majd minden egymást követő elemet kinyomtat a konzolra. newArraymost egy max kupac. Vegye figyelembe, hogy az előző példához hasonlóan a PriorityQueue használatával a számok ki vannak írva: gyökér, gyökér jobb gyermeke szülőként, gyökér bal gyermeke szülőként, első jobb gyermek jobb gyermeke szülőként, első bal gyermeke bal-gyermek szülőként, jobb-gyermek első bal-gyermek szülőként, bal-gyermek első jobb-gyermek szülőként stb. Ezek kissé eltérő sorrendben vannak, mint a PriorityQueue használatakor, mivel az összehasonlítás az egymást követő elemek között történik míg a maxheapify példában a csomópont összehasonlításra kerül a tömb következő két egymást követő elemével, és a legnagyobb értékre cseréli. Röviden, két különböző algoritmust használnak. Mindkettő maximális kupacot hoz létre.

Következtetés

Tehát itt megvizsgáltuk a max kupacot, és azt, hogy hogyan hozható létre PriorityQueue vagy Max Heapify algoritmussal. A PriorityQueue használata a reverseOrder() - vel egy remek módja ennek és az ajánlott módszernek. Azonban tanulmányozhatja ezeket a példákat, és megírhatja saját módszereit, mivel ez egy jó kódolási gyakorlat, amely segít sikeresen elkészíteni a Java Junior interjút.