Heap massimo in Java

L'albero binario

In Java esistono molti tipi diversi di strutture dati. L'heap è basato su una struttura ad albero chiamata albero binario . Un albero binario è costituito da nodi, ognuno dei quali può avere un massimo di 2 nodi figli: Un albero binario è costituito da un nodo genitore che può avere da 0 a 2 nodi. Può avere un nodo figlio sinistro e/o un nodo figlio destro o nessun nodo. In un albero binario completo, tutti i nodi sono pieni tranne l'ultimo livello che può essere pieno, ma non è necessario che sia pieno. L'ultimo livello, l'ennesimo livello, può avere da 1 a 2n nodi, dove il primo è a n = 0 ed è la radice.

Max Mucchio

Max heap (o maxheap) è un albero binario completo . La cosa importante è che il nodo genitore DEVE avere un valore maggiore o uguale a quello dei nodi figlio sinistro e destro. Se questo non viene rispettato, non hai un max heap. Min heap, d'altra parte, è l'opposto con la radice come valore più piccolo con nodi successivi che aumentano di valore; ogni nodo figlio ha un valore maggiore o uguale al suo genitore. È anche un albero binario completo. Un esempio di max heap è: Max heap può essere costruito da un array. Questo array sarà pensato in termini di un albero. Per un heap, se la radice (nodo padre superiore dell'albero) è memorizzata nella posizione (indice) n, viene definita per array, theArray , come theArray[n]. I nodi figlio sinistro e destro sono, quindi, rispettivamente in theArray[2n+1] e theArray[2n+2] . Per l'heap massimo, la radice è in theArray[0] . Per il livello n, radice n = 0: theArr[n] è il nodo padre theArr[(2*n)+1] è il nodo figlio sinistro theArr[(2*n)+2] è il nodo figlio destro

La classe PriorityQueue

Gli heap in Java possono essere implementati utilizzando la classe PriorityQueue . Le PriorityQueues vengono utilizzate per trovare l'elemento più o meno importante in una raccolta. La classe PriorityQueue può essere trovata in java.util.package . PriorityQueues deve essere formato da oggetti confrontabili in modo che vengano inseriti in un ordine particolare nella coda. PriorityQueue può avere un comparatore in modo che venga effettuato un confronto tra gli oggetti e la coda formata in base a questo confronto. Un esempio è:

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

Dare output: In questo esempio, la dimensione predefinita di intQueue è 11, quindi non è stata dichiarata (di solito il primo argomento prima del comparatore) e il comparatore è stato dato come: Questo farà un confronto tra gli elementi in intQueue e li ordinerà in lunghezze di array di ordine crescente.

Implementazione di PriorityQueue per creare un heap massimo

L' impostazione predefinita della classe PriorityQueue è l'heap minimo senza un comparatore. Min heap è l'opposto di max heap e quindi la radice è il valore più piccolo e i successivi nodi figlio sono maggiori o uguali alla radice e ai successivi nodi parentali. Per questo motivo, per max heap, è necessario utilizzare reverseOrder() dal framework Collections di Java come comparatore. Ciò assicurerà di ottenere un heap massimo e non un heap minimo. Questa classe ha metodi utili come add() , contains() , remove() , poll() e peek() . Gli elementi vengono aggiunti alla coda e possono essere in qualsiasi ordine. La nuova coda PriorityQueue memorizzerà questi elementi come max heap in ordine inverso. Quando la coda viene scritta, l'ordine sarà: Root Left-child con root come parent (Left-child_1) Right-child con root come parent (Right-child_1) Left-child con Left-child_1 come parent (Left-child_2 ) Figlio destro con figlio sinistro_1 come genitore (Figlio destro_2) Figlio sinistro con figlio destro_1 come genitore (Figlio sinistro_3) Figlio destro con figlio destro_1 come genitore (Figlio destro_3) Figlio sinistro con figlio sinistro_2 come genitore (Left-child_4) Right-child con Left-child_2 come genitore (Right-child_4), eccIl codice seguente è un esempio di come viene creato un max heap (maxheap) in java. La prima cosa da fare è riempire un array con i valori per i quali verrà creato l'heap massimo. Questo è chiamato theArray . Successivamente, viene creato un PriorityQueue , theQueue , e quindi gli elementi di theArray vengono aggiunti a questo. Questo utilizza il metodo add() , ad esempio theQueue.add(10) per aggiungere 10 alla fine della coda. Per illustrare alcune delle funzionalità della classe PriorityQueue , viene quindi utilizzato il metodo peek() per trovare l'intestazione dell'heap, e questo è il valore massimo, in questo caso, 99. L'attività successiva consiste nel controllare la dimensione dell'heap usando la dimensione()che risulta essere 9 e questo viene stampato sulla console. Il metodo writeMaxHeap scrive gli elementi nella coda in ordine di root, figlio sinistro con root come genitore, figlio destro con root come genitore, figlio sinistro con il primo figlio sinistro come genitore, figlio destro con il primo figlio sinistro come genitore, figlio destro con il primo figlio destro come genitore, figlio sinistro con il primo figlio destro come genitore ecc., con valori successivi usando i figli sinistro e destro come genitori nello stesso ordine di cui sopra. Il metodo PriorityQueue contains(J) viene utilizzato per scoprire se un elemento specifico, J, è in una coda. In questo caso cerchiamo J = 10. Nel nostro esempio, è vero che questo è nella coda, quindi viene scritto nella console come vero. Un altro metodo PriorityQueue , remove(J) viene quindi utilizzato per rimuovere J = 10 da theQueue . Per illustrare meglio la funzionalità di PriorityQueue , il metodo poll() viene utilizzato per rimuovere l'elemento head (valore massimo) utilizzando un ciclo while , rimuovendo ogni volta l'elemento head nella nuova coda e diminuendo la dimensione della coda di uno ogni volta. Questo accade nel metodo writeQueuechiamato dal principale. Ogni volta che l'elemento rimosso viene stampato sulla console. Alla fine la coda originale non avrà più elementi. Gli elementi stampati sono l'heap massimo in ordine decrescente di valore, dove viene stampata ogni volta l'inizio della coda.

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

Produzione:

Max Heapify

L'algoritmo Max Heapify viene utilizzato per garantire che un albero binario sia un max heap. Se ci troviamo su un nodo, n, e i suoi nodi figlio, sinistra e destra sono anch'essi max heap, allora ottimo, abbiamo un max heap. Se questo non è il caso in tutto l'albero, allora non abbiamo un max heap. L'algoritmo Max Heapify viene utilizzato per ordinare l'albero in modo che aderisca ai principi di maxheap. Max Heapify funziona su un solo nodo. Se il requisito è che l'array sia un array max heap, tutti i sottoalberi devono essere convertiti in maxheap prima della radice, uno alla volta. L'algoritmo deve essere utilizzato su ogni nodo. Questo verrà fatto su N/2 nodi (le foglie rispetteranno i requisiti di max heap). La complessità temporale dell'heap è O(NlogN) e per un nodo all'altezza X, la complessità temporale è O(X). Il codice seguente mostra come maxheapify un albero (un 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();
       }
  }
}

Dare output: In questo codice, l'Array viene creato e riempito di numeri. Viene creato un secondo array, newArray , e questa volta conterrà il risultato del metodo, maxheapCreate , l'array max heap. Il metodo maxHeapCreate viene chiamato da main e qui un nuovo array, theNewArr , viene creato e riempito con i risultati maxHeapify . Questo viene fatto eseguendo il looping di oltre la metà della dimensione dell'array di input. Per ogni passaggio del ciclo, viene chiamato il metodo maxHeapify , iniziando dall'elemento al centro dell'array e terminando con il primo. Per ogni chiamata di maxHeapify, il figlio sinistro e il figlio destro del nodo genitore, i, vengono trovati e vengono eseguiti controlli per trovare quale sia il più grande dei tre, definendolo come maxVal . Se maxVal non è uguale al nodo padre, viene eseguito uno scambio in modo che il nodo padre e maxVal vengano scambiati e quindi maxHeapify viene chiamato di nuovo questa volta su maxVal e vengono eseguiti gli stessi passaggi di prima. Alla fine verrà creato il max heap e non ci saranno più iterazioni da eseguire. L'array aggiornato, array , viene ora restituito a main come newArray e quindi ogni elemento consecutivo viene stampato nella console. newArrayora è un max heap. Nota che come nell'esempio precedente usando PriorityQueue i numeri sono scritti: root, figlio destro di root come genitore, figlio sinistro di root come genitore, figlio destro del primo figlio destro come genitore, figlio sinistro del primo figlio sinistro come genitore, figlio destro del primo figlio sinistro come genitore, figlio sinistro del primo figlio destro come genitore, ecc. Sono in un ordine leggermente diverso rispetto a quando si utilizza PriorityQueue perché il confronto viene eseguito tra elementi consecutivi mentre nell'esempio maxheapify, il nodo viene confrontato con i successivi due elementi successivi nell'array e scambiato con il valore più grande. In breve, vengono utilizzati due diversi algoritmi. Entrambi creano un max heap.

Conclusione

Quindi qui abbiamo esaminato l'heap massimo e come può essere creato con un algoritmo PriorityQueue o Max Heapify. L'uso di PriorityQueue con reverseOrder() è un modo accurato per farlo e il metodo consigliato. Tuttavia, puoi studiare questi esempi e scrivere i tuoi metodi poiché questo sarà un buon esercizio di programmazione che ti aiuterà ad avere successo nel tuo colloquio per Java Junior.