Max Heap i Java

Det binära trädet

I Java finns det många olika typer av datastrukturer. Högen är baserad på en trädstruktur som kallas ett binärt träd . Ett binärt träd består av noder, som var och en kan ha maximalt 2 underordnade noder: Ett binärt träd består av en föräldernod som kan ha från 0 till 2 noder. Den kan ha en vänster-under-nod och/eller en höger-under-nod, eller inga noder alls. I ett komplett binärt träd är alla noder fyllda förutom den sista nivån som kan vara full, men inte behöver vara full. Den sista nivån, den n:e nivån, kan ha från 1 till 2n noder, där den första är vid n = 0 och är roten.

Max Heap

Max heap (eller maxheap) är ett komplett binärt träd . Det viktiga med det är att föräldranoden MÅSTE ha ett värde som är större än eller lika med det för vänster- och högerundernoderna. Om detta inte följs har du ingen maxhög. Min heap, å andra sidan, är motsatsen med roten som det minsta värdet med successiva noder som ökar i värde; varje underordnad nod har ett värde som är större än eller lika med dess överordnade. Det är också ett komplett binärt träd. Ett exempel på en maxhög är: Maxhög kan byggas från en array. Denna array kommer att ses som ett träd. För en hög, om roten, (trädets översta överordnade nod) är lagrad i position (index) n, definieras den för array, theArray , som theArray[n]. De vänstra och högra underordnade noderna är därför vid theArray[2n+1] respektive theArray[2n+2] . För maxhögen är roten vid theArray[0] . För nivån n är roten n = 0: theArr[n] är föräldernoden theArr[(2*n)+1] är den vänstra underordnade noden theArr[(2*n)+2] är den högra barnnoden

Klassen PriorityQueue

Heaps i Java kan implementeras med PriorityQueue Class. PriorityQueue används för att hitta det viktigaste eller minst viktiga föremålet i en samling. Klassen PriorityQueue finns i java.util.package . Prioritetsköer måste bildas av objekt som är jämförbara så att de placeras i en viss ordning i kön. PriorityQueue kan ha en komparator så att en jämförelse mellan objekten görs och den kön som bildas enligt denna jämförelse. Ett exempel är:

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

Ge utdata: I det här exemplet är standardstorleken för intQueue 11, så har inte angetts (vanligtvis det första argumentet före komparatorn) och komparatorn har angetts som: Detta kommer att göra en jämförelse mellan objekten i intQueue och sortera dem i arraylängder i stigande ordning.

Implementering av PriorityQueue för att skapa en Max Heap

PriorityQueue Class är standard till min heap utan en komparator. Minhög är motsatsen till maxhög och så roten är det minsta värdet och på varandra följande underordnade noder är större eller lika med roten och efterföljande föräldranoder. Av denna anledning, för max heap, är det nödvändigt att använda reverseOrder() från Javas samlingsramverk som komparator. Detta kommer att säkerställa att vi får en maxhög och inte en minhög. Den här klassen har användbara metoder som add() , contains() , remove() , poll() , och peek() . Element läggs till i kön och kan vara i valfri ordning. Den nya PriorityQueue-kön kommer att lagra dessa element som en maxhög i omvänd ordning. När kön skrivs ut blir ordningen: Rot Vänster-barn med rot som förälder (Vänster-barn_1) Höger-barn med rot som förälder (Höger-barn_1) Vänster-barn med Vänster-barn_1 som förälder (Vänster-barn_2) ) Höger-barn med Vänster-barn_1 som förälder (Höger-barn_2) Vänster-barn med Höger-barn_1 som förälder (Vänster-barn_3) Höger-barn med Höger-barn_1 som förälder (Höger-barn_3) Vänster-barn med Vänster-barn_2 som förälder (Vänster-barn_4) Höger-barn med Vänster-barn_2 som förälder (Höger-barn_4), etcFöljande kod är ett exempel på hur en maxheap (maxheap) skapas i java. Det första du ska göra är att fylla en array med de värden för vilka maxhögen kommer att skapas. Detta kallas theArray . Därefter skapas en PriorityQueue , theQueue , och sedan läggs elementen från theArray till denna. Detta använder metoden add() , t.ex. theQueue.add(10) för att lägga till 10 i slutet av kön. För att illustrera en del av funktionaliteten i PriorityQueue Class används sedan metoden peek() för att hitta högens huvud, och detta är maxvärdet, i det här fallet, 99. Nästa uppgift är att kontrollera storleken på högen använder storlek()som visar sig vara 9 och detta skrivs ut till konsolen. Metod writeMaxHeap skriver ut elementen i kön i rotordning, vänster-barn med rot som förälder, höger-barn med rot som förälder, vänster-barn med första vänster-barn som förälder, höger-barn med första vänster-barn som förälder, höger-barn med första höger-barn som förälder, vänster-barn med första höger-barn som förälder etc, med efterföljande värden som använder vänster och höger barn som föräldrar i samma ordning som ovan. PriorityQueue - metoden contains(J) används för att ta reda på om ett specifikt element, J, finns i en kö. I det här fallet letar vi efter J = 10. I vårt exempel är det sant att detta är i kön så detta skrivs ut till konsolen som sant. En annan PriorityQueue- metod, remove(J) används sedan för att ta bort J = 10 från theQueue . För att illustrera mer av funktionaliteten hos PriorityQueue , används metoden poll() för att ta bort head-elementet (maximalt värde) med hjälp av en while- loop, varje gång man tar bort head-elementet i den nya kön och minskar kön i storlek med en varje gång. Detta händer i metoden writeQueueanropas från main. Varje gång elementet tas bort skrivs det ut på konsolen. Den ursprungliga kön kommer så småningom att ha inga element kvar. De utskrivna elementen är maxhögen i fallande värdeordning, där köns huvud skrivs ut varje gång.

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

Produktion:

Max Heapify

Max Heapify-algoritmen används för att säkerställa att ett binärt träd är en maxhög. Om vi ​​är vid en nod, n, och dess undernoder, vänster och höger är också maxhögar själva, så bra, vi har en maxhög. Om så inte är fallet i hela trädet så har vi ingen maxhög. Max Heapify-algoritmen används för att sortera trädet så att det följer maxheap-principerna. Max Heapify fungerar bara på en nod. Om kravet är att arrayen är en maxheap-array, måste alla underträd konverteras till maxheap före roten, ett i taget. Algoritmen måste användas på varje nod. Detta kommer att göras på N/2 noder (löven kommer att följa maxkraven för högen). Tidskomplexiteten för högen är O(NlogN), och för en nod på höjden X är tidskomplexiteten O(X). Följande kod visar hur man maxheapify ett träd (en array).

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

Ge utdata: I den här koden skapas theArray och fylls med siffror. En andra array, newArray , skapas och den här gången kommer den att innehålla resultatet av metoden maxheapCreate , max heap arrayen. Metoden maxHeapCreate anropas från main , och här skapas en ny array, theNewArr , som fylls med maxHeapify- resultaten. Detta görs genom att loopa över halva storleken på inmatningsmatrisen. För varje pass av loopen kallas metoden maxHeapify , som börjar vid elementet i mitten av arrayen och slutar med det första. För varje samtal av maxHeapify, vänstra underordnade och högra underordnade underordnade noden, i, hittas och kontroller görs för att hitta vilken som är störst av de tre, och definierar det som maxVal . Om maxVal inte är lika med föräldernoden så görs ett byte så att föräldernoden och maxVal byts ut och sedan anropas maxHeapify igen denna gång på maxVal och samma steg utförs som tidigare. Så småningom kommer maxhögen att skapas och det kommer inte att finnas fler iterationer att utföra. Den uppdaterade arrayen, array , returneras nu till main som newArray och sedan skrivs varje på varandra följande element ut till konsolen. newArrayär nu en maxhög. Notera att som i det föregående exemplet med PriorityQueue skrivs siffrorna ut: rot, höger-barn till rot som förälder, vänster-barn till rot som förälder, höger-barn till första höger-barn som förälder, vänster-barn till första vänster-barn som förälder, höger-barn till första vänster-barn som förälder, vänster-barn till första höger-barn som förälder, etc. De är i en något annorlunda ordning än när man använder PriorityQueue eftersom jämförelsen görs mellan på varandra följande element medan i exemplet maxheapify jämförs noden med nästa två på varandra följande element i arrayen och byts ut mot det största värdet. Kort sagt, två olika algoritmer används. Båda skapar en maxhög.

Slutsats

Så här har vi tittat på max heap och hur det kan skapas med antingen en PriorityQueue eller en Max Heapify-algoritm. Att använda PriorityQueue med reverseOrder() är ett snyggt sätt att göra detta och den rekommenderade metoden. Du kan dock studera dessa exempel och skriva dina egna metoder eftersom detta kommer att vara en bra kodningsövning som hjälper dig att lyckas i din intervju för Java Junior.