Max Heap i Java

Det binære treet

I Java er det mange forskjellige typer datastrukturer. Haugen er basert på en trestruktur kalt et binært tre . Et binært tre består av noder, som hver kan ha maksimalt 2 underordnede noder: Et binært tre består av en overordnet node som kan ha fra 0 til 2 noder. Den kan ha en venstre-barn-node og/eller en høyre-barn-node, eller ingen noder i det hele tatt. I et komplett binært tre er alle noder fylt bortsett fra det siste nivået som kan være fullt, men ikke trenger å være fullt. Det siste nivået, det n'te nivået, kan ha fra 1 til 2n noder, hvor det første er ved n = 0 og er roten.

Max Heap

Max heap (eller maxheap) er et komplett binært tre . Det viktige med det er at den overordnede noden MÅ ha en verdi som er større enn eller lik verdien til venstre- og høyre-undernoden. Dersom dette ikke overholdes, har du ikke maks haug. Min haug, derimot, er det motsatte med roten som den minste verdien med suksessive noder økende i verdi; hver underordnede node har en verdi større enn eller lik dens overordnede node. Det er også et komplett binært tre. Et eksempel på en maks haug er: Maks haug kan bygges fra en matrise. Denne matrisen vil bli tenkt på i form av et tre. For en haug, hvis roten, (øverste overordnede node i treet) er lagret i posisjon (indeks) n, er den definert for array, theArray , som theArray[n]. Venstre og høyre underordnede noder er derfor ved henholdsvis Array[2n+1] og Array[2n+2] . For den maksimale haugen er roten ved theArray[0] . For nivået n, roten n = 0: theArr[n] er den overordnede noden theArr[(2*n)+1] er den venstre underordnede noden theArr[(2*n)+2] er den høyre barnenoden

Prioritetskø-klassen

Heaps i Java kan implementeres ved å bruke PriorityQueue Class. PriorityQueue brukes til å finne det viktigste eller minst viktige elementet i en samling. PriorityQueue- klassen finner du i java.util.package . Prioritetskøer må dannes av objekter som er sammenlignbare slik at de plasseres i en bestemt rekkefølge i køen. PriorityQueue kan ha en komparator slik at det gjøres en sammenligning mellom objektene og køen som dannes i henhold til denne sammenligningen. Et eksempel er:

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

Gir utgang: I dette eksemplet er standardstørrelsen til intQueue 11, så den har ikke blitt oppgitt (vanligvis det første argumentet før komparatoren) og komparatoren er gitt som: Dette vil gjøre en sammenligning mellom elementene i intQueue og sortere dem i matriselengder i stigende rekkefølge.

Implementering av PriorityQueue for å lage en maksimal haug

PriorityQueue Class er standard til min heap uten en komparator. Min haug er det motsatte av maks haug, så roten er den minste verdien og påfølgende barnenoder er større eller lik roten og påfølgende foreldrenoder. Av denne grunn, for max heap, er det nødvendig å bruke reverseOrder() fra Javas Collections-rammeverk som komparator. Dette vil sikre at vi får en maks haug og ikke en min haug. Denne klassen har nyttige metoder som add() , contains() , remove() , poll() , og peek() . Elementer legges til i køen og kan være i hvilken som helst rekkefølge. Den nye PriorityQueue-køen vil lagre disse elementene som en maksimal haug i omvendt rekkefølge. Når køen er skrevet ut vil rekkefølgen være: Rot Venstre-barn med rot som forelder (Venstre-barn_1) Høyre-barn med rot som forelder (Høyre-barn_1) Venstre-barn med Venstre-barn_1 som forelder (Venstre-barn_2) ) Høyre-barn med Venstre-barn_1 som forelder (Høyre-barn_2) Venstre-barn med Høyre-barn_1 som forelder (Venstre-barn_3) Høyre-barn med Høyre-barn_1 som forelder (Høyre-barn_3) Venstre-barn med Venstre-barn_2 som forelder (Venstre-barn_4) Høyre-barn med Venstre-barn_2 som forelder (Høyre-barn_4), osv.Følgende kode er et eksempel på hvordan en max heap (maxheap) lages i java. Det første du må gjøre er å fylle en matrise med verdiene som den maksimale heapen vil bli opprettet for. Dette kalles theArray . Deretter opprettes en PriorityQueue , theQueue , og deretter legges elementene fra theArray til denne. Dette bruker metoden add() , f.eks. theQueue.add(10) for å legge til 10 på slutten av køen. For å illustrere noe av funksjonaliteten til PriorityQueue Class , brukes metode peek() for å finne hodet til haugen, og dette er maksimumsverdien, i dette tilfellet, 99. Neste oppgave er å sjekke størrelsen på haugen. bruker størrelse()som er funnet å være 9 og dette skrives ut til konsollen. Metode writeMaxHeap skriver ut elementene i køen i rekkefølge etter rot, venstre-barn med rot som forelder, høyre-barn med rot som forelder, venstre-barn med første venstre-barn som forelder, høyre-barn med første venstre-barn som forelder, høyre-barn med første høyre-barn som forelder, venstre-barn med første høyre-barn som forelder osv., med påfølgende verdier som bruker venstre og høyre barn som foreldre i samme rekkefølge som ovenfor. PriorityQueue - metoden contains(J) brukes til å finne ut om et spesifikt element, J, er i en kø. I dette tilfellet ser vi etter J = 10. I vårt eksempel er det sant at dette er i køen så dette skrives ut til konsollen som sant. En annen PriorityQueue- metode, remove(J) brukes deretter til å fjerne J = 10 fra theQueue . For å illustrere mer av funksjonaliteten til PriorityQueue , brukes metoden poll() for å fjerne head-elementet (maksimal verdi) ved å bruke en while- løkke, hver gang man fjerner head-elementet i den nye køen og reduserer køen i størrelse med én hver gang. Dette skjer i metoden writeQueueringte fra hovedtelefonen. Hver gang elementet fjernes, skrives det ut på konsollen. Den opprinnelige køen vil til slutt ikke ha noen elementer igjen. De utskrevne elementene er den maksimale haugen i synkende rekkefølge av verdi, hvor hodet på køen skrives ut hver gang.

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

Produksjon:

Max Heapify

Max Heapify-algoritmen brukes til å sikre at et binært tre er en maksimal haug. Hvis vi er ved en node, n, og dens underordnede noder, venstre og høyre er også maks hauger i seg selv, så flott, vi har en maks haug. Hvis dette ikke er tilfelle i hele treet så har vi ikke en maks haug. Max Heapify-algoritmen brukes til å sortere treet slik at det følger maxheap-prinsippene. Max Heapify fungerer på bare én node. Hvis kravet er at arrayet er en max heap array, må alle undertrær konverteres til maxheap før roten, ett om gangen. Algoritmen må brukes på hver node. Dette vil bli gjort på N/2 noder (bladene vil overholde kravene til maksimal haug). Tidskompleksiteten til haugen er O(NlogN), og for en node i høyden X er tidskompleksiteten O(X). Følgende kode viser hvordan du maxheapify et tre (en matrise).

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

Gir utgang: I denne koden er theArray opprettet og fylt med tall. En andre array, newArray , opprettes og denne gangen vil den inneholde resultatet av metoden, maxheapCreate , max heap array. Metoden maxHeapCreate kalles fra main , og her opprettes en ny array, theNewArr , som fylles med maxHeapify- resultatene. Dette gjøres ved å sløyfe over halvparten av størrelsen på inngangsmatrisen. For hver pass av loopen kalles metoden maxHeapify , som starter ved elementet i midten av matrisen og slutter med det første. For hvert anrop til maxHeapify, venstre underordnede og høyre underordnede underordnede node, i, blir funnet, og det blir sjekket for å finne hvilken som er størst av de tre, og definerer det som maxVal . Hvis maxVal ikke er lik den overordnede noden, gjøres en swap slik at den overordnede noden og maxVal byttes og deretter kalles maxHeapify igjen denne gangen på maxVal og de samme trinnene utføres som før. Til slutt vil den maksimale haugen bli opprettet, og det vil ikke være flere iterasjoner å utføre. Den oppdaterte arrayen, array , returneres nå til main som newArray og deretter skrives hvert påfølgende element ut til konsollen. newArrayer nå en maks haug. Merk at som i forrige eksempel ved bruk av PriorityQueue skrives tallene ut: rot, høyre-barn av rot som forelder, venstre-barn av rot som forelder, høyre-barn av første høyre-barn som forelder, venstre-barn av første venstre-barn som forelder, høyre-barn av første venstre-barn som forelder, venstre-barn av første høyre-barn som forelder, osv. De er i en litt annen rekkefølge enn når du bruker PriorityQueue fordi sammenligningen gjøres mellom påfølgende elementer mens i maxheapify-eksemplet blir noden sammenlignet med de neste to påfølgende elementene i matrisen og byttet for den største verdien. Kort fortalt brukes to forskjellige algoritmer. Begge skaper en maks haug.

Konklusjon

Så her har vi sett på max heap og hvordan det kan lages med enten en PriorityQueue eller en Max Heapify algoritme. Å bruke PriorityQueue med reverseOrder() er en fin måte å gjøre dette på og den anbefalte metoden. Du kan imidlertid studere disse eksemplene og skrive dine egne metoder siden dette vil være en god kodeøvelse som hjelper deg til å lykkes i intervjuet for Java Junior.