Max Heap în Java

Arborele binar

În Java, există multe tipuri diferite de structuri de date. Heap-ul se bazează pe o structură arborescentă numită arbore binar . Un arbore binar este format din noduri, fiecare dintre acestea putând avea maximum 2 noduri copil: Un arbore binar este format dintr-un nod părinte care poate avea de la 0 la 2 noduri. Poate avea un nod copil stâng și/sau un nod copil dreapta sau nici un nod. Într-un arbore binar complet, toate nodurile sunt umplute, cu excepția ultimului nivel care poate fi plin, dar nu trebuie să fie plin. Ultimul nivel, al n-lea nivel, poate avea de la 1 la 2n noduri, unde primul este la n = 0 și este rădăcina.

Max Heap

Max heap (sau maxheap) este un arbore binar complet . Important este că nodul părinte TREBUIE să aibă o valoare mai mare sau egală cu cea a nodurilor secundare stânga și dreapta. Dacă acest lucru nu este respectat, nu aveți o grămadă maximă. Min heap, pe de altă parte, este opusul cu rădăcina ca cea mai mică valoare cu noduri succesive care cresc în valoare; fiecare nod copil are o valoare mai mare sau egală cu părintele său. Este, de asemenea, un arbore binar complet. Un exemplu de heap maxim este: Heap maxim poate fi construit dintr-o matrice. Această matrice va fi gândită în termeni de arbore. Pentru un heap, dacă rădăcina (nodul părinte superior al arborelui) este stocată la poziția (index) n, este definită pentru matrice, theArray , ca theArray[n]. Nodurile secundare stânga și dreapta sunt, prin urmare, la Matrice[2n+1] și, respectiv, Matrice[2n+2] . Pentru heap-ul maxim, rădăcina este la theArray[0] . Pentru nivelul n, rădăcina n = 0: theArr[n] este nodul părinte theArr[(2*n)+1] este nodul copil stâng theArr[(2*n)+2] este nodul copil drept

Clasa PriorityQueue

Mulțile în Java pot fi implementate folosind clasa PriorityQueue . PriorityQueue sunt folosite pentru a găsi elementul cel mai sau cel mai puțin important dintr-o colecție. Clasa PriorityQueue poate fi găsită în java.util.package . PriorityQueues trebuie să fie formate din obiecte care sunt comparabile, astfel încât să fie plasate într-o anumită ordine în coadă. PriorityQueue poate avea un comparator astfel încât să se facă o comparație între obiecte și coada formată conform acestei comparații. Un exemplu este:

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

Oferă rezultate: În acest exemplu, dimensiunea implicită a intQueue este 11, deci nu a fost specificată (de obicei primul argument înaintea comparatorului) și comparatorul a fost dat ca: Aceasta va face o comparație între elementele din intQueue și le va sorta în lungimi de matrice în ordine crescătoare.

Implementarea PriorityQueue pentru a crea un heap maxim

Clasa PriorityQueue este implicit la min heap fără un comparator. Heap min este opusul heap max și, prin urmare, rădăcina este cea mai mică valoare, iar nodurile secundare succesive sunt mai mari sau egale cu rădăcina și nodurile parentale ulterioare. Din acest motiv, pentru heap maxim, este necesar să folosiți reverseOrder() din cadrul Java’s Collections ca comparator. Acest lucru ne va asigura că obținem un heap maxim și nu un heap minim. Această clasă are metode utile, cum ar fi add() , contains() , remove() , poll() și peek() . Elementele sunt adăugate la coadă și pot fi în orice ordine. Noua coadă PriorityQueue va stoca acele elemente ca un heap maxim în ordine inversă. Când coada este scrisă, ordinea va fi: Rădăcină Left-child cu rădăcină ca părinte (Left-child_1) Drept-copil cu rădăcină ca părinte (Right-child_1) Stânga-copil cu Left-child_1 ca părinte (Left-child_2) ) Copil-dreapta cu copil-stânga_1 ca părinte (copil-dreapta_2) Copil-stânga cu copil-dreapta_1 ca părinte (copil-stânga_3) Copil-dreapta cu copil-dreapta_1 ca părinte (copil-dreapta_3) Copil stânga cu copil-stânga_2 ca părinte (Left-child_4) Dreptul-copil cu Left-child_2 ca părinte (Right-child_4), etc.Următorul cod este un exemplu despre cum este creat un heap maxim (maxheap) în java. Primul lucru de făcut este să completați o matrice cu valorile pentru care va fi creat heap-ul maxim. Aceasta se numește theArray . Apoi, este creată o PriorityQueue , theQueue , iar apoi elementele din theArray sunt adăugate la aceasta. Aceasta folosește metoda add() , de exemplu theQueue.add(10) pentru a adăuga 10 la sfârșitul cozii. Pentru a ilustra unele dintre funcționalitățile clasei PriorityQueue , metoda peek() este apoi utilizată pentru a găsi capul heap-ului, iar aceasta este valoarea maximă, în acest caz, 99. Următoarea sarcină este să verificați dimensiunea heap-ului. folosind dimensiunea ()care se dovedește a fi 9 și acesta este imprimat pe consolă. Metoda writeMaxHeap scrie elementele din coadă în ordinea rădăcinii, stânga-copil cu rădăcină ca părinte, dreapta-copil cu rădăcină ca părinte, stânga-copil cu primul stâng-copil ca părinte, dreapta-copil cu primul stânga-copil ca părinte, copilul drept cu primul copil drept ca părinte, copil stânga cu primul copil drept ca părinte etc, cu valorile ulterioare folosind copiii din stânga și din dreapta ca părinți în aceeași ordine ca mai sus. Metoda PriorityQueue contains(J) este folosită pentru a afla dacă un anumit element, J, se află într-o coadă . În acest caz, căutăm J = 10. În exemplul nostru, este adevărat că aceasta este în coadă, așa că aceasta este scrisă pe consolă ca fiind adevărat. O altă metodă PriorityQueue , remove(J) este apoi folosită pentru a elimina J = 10 din theQueue . Pentru a ilustra mai mult funcționalitatea PriorityQueue , metoda poll() este folosită pentru a elimina elementul head (valoarea maximă) folosind o buclă while , de fiecare dată eliminând elementul head din noua coadă și micșorând dimensiunea cozii cu câte o dată de fiecare dată. Acest lucru se întâmplă în metoda writeQueuesunat din main. De fiecare dată când elementul îndepărtat este imprimat pe consolă. În cele din urmă, coada originală nu va mai avea niciun element. Elementele tipărite sunt heap-ul maxim în ordinea descrescătoare a valorii, unde capul cozii este tipărit de fiecare dată.

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

Ieșire:

Max Heapify

Algoritmul Max Heapify este utilizat pentru a se asigura că un arbore binar este un heap maxim. Dacă ne aflăm la un nod, n, iar nodurile sale secundare, stânga și dreapta sunt, de asemenea, grămezi maxime în sine, atunci grozav, avem un heap maxim. Dacă acest lucru nu este cazul în întregul copac, atunci nu avem o grămadă maximă. Algoritmul Max Heapify este folosit pentru a sorta arborele astfel încât să adere la principiile maxheap. Max Heapify funcționează pe un singur nod. Dacă cerința este ca matricea să fie o matrice maxheap, atunci toți sub-arborele trebuie convertiți în maxheap înainte de rădăcină, unul câte unul. Algoritmul trebuie utilizat pe fiecare nod. Acest lucru se va face pe N/2 noduri (frunzele vor respecta cerințele maxime de heap). Complexitatea de timp a heap-ului este O(NlogN), iar pentru un nod la înălțimea X, complexitatea de timp este O(X). Următorul cod arată cum să maximizați un copac (o matrice).

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

Oferă rezultate: În acest cod, Array este creat și umplut cu numere. Este creată o a doua matrice, newArray , și de data aceasta va conține rezultatul metodei, maxheapCreate , matricea maxim heap. Metoda maxHeapCreate este apelată din main , iar aici este creată o nouă matrice, theNewArr , care este completată cu rezultatele maxHeapify . Acest lucru se face prin bucla peste jumătate din dimensiunea matricei de intrare. Pentru fiecare trecere a buclei, metoda maxHeapify este apelată începând cu elementul din mijlocul matricei și terminând cu primul. Pentru fiecare apel de maxHeapify, sunt găsite copilul stâng și copilul drept al nodului părinte, i, și se fac verificări pentru a găsi care este cel mai mare dintre cele trei, definindu-l ca maxVal . Dacă maxVal nu este egal cu nodul părinte, atunci se face o schimbare, astfel încât nodul părinte și maxVal să fie schimbate și apoi maxHeapify este apelat din nou de data aceasta pe maxVal și se efectuează aceiași pași ca înainte. În cele din urmă, heap-ul maxim va fi creat și nu vor mai fi iterații de efectuat. Matricea actualizată, array , este acum returnată la main ca newArray și apoi fiecare element consecutiv este imprimat pe consolă. newArrayeste acum o grămadă maximă. Rețineți că, la fel ca în exemplul anterior, folosind PriorityQueue, numerele sunt scrise: rădăcină, copilul din dreapta al rădăcinii ca părinte, copilul din stânga al rădăcinii ca părinte, copilul din dreapta al primului copil din dreapta ca părinte, copilul din stânga al primului stanga-copil ca parinte, dreapta-copil al primului stanga-copil ca parinte, stanga-copil al primului drept-copil ca parinte etc. Sunt intr-o ordine putin diferita de cele cand se foloseste PriorityQueue deoarece comparatia se face intre elemente consecutive în timp ce în exemplul maxheapify, nodul este comparat cu următoarele două elemente succesive din matrice și schimbat pentru cea mai mare valoare. Pe scurt, sunt utilizați doi algoritmi diferiți. Ambele creează un heap maxim.

Concluzie

Deci aici ne-am uitat la max heap și cum poate fi creat fie cu un algoritm PriorityQueue , fie cu un algoritm Max Heapify. Utilizarea PriorityQueue cu reverseOrder() este o modalitate bună de a face acest lucru și metoda recomandată. Cu toate acestea, puteți studia aceste exemple și scrie propriile metode, deoarece acesta va fi un exercițiu de codificare bun, care vă va ajuta să reușiți la interviul pentru Java Junior.