Max Heap en Java

L'arbre binaire

En Java, il existe de nombreux types de structures de données. Le tas est basé sur une structure arborescente appelée arbre binaire . Un arbre binaire est constitué de nœuds, chacun pouvant avoir au maximum 2 nœuds enfants : Un arbre binaire est constitué d'un nœud parent qui peut avoir de 0 à 2 nœuds. Il peut avoir un nœud enfant gauche et/ou un nœud enfant droit, ou aucun nœud du tout. Dans un arbre binaire complet, tous les nœuds sont remplis à l'exception du dernier niveau qui peut être plein, mais n'a pas besoin d'être plein. Le dernier niveau, le nième niveau, peut avoir de 1 à 2n nœuds, où le premier est à n = 0 et est la racine.

Tas maximum

Max heap (ou maxheap) est un arbre binaire complet . La chose importante à ce sujet est que le nœud parent DOIT avoir une valeur supérieure ou égale à celle des nœuds enfants gauche et droit. Si cela n'est pas respecté, vous n'avez pas de tas maximum. Le tas min, en revanche, est le contraire avec la racine comme la plus petite valeur avec des nœuds successifs dont la valeur augmente ; chaque nœud enfant a une valeur supérieure ou égale à son parent. C'est aussi un arbre binaire complet. Un exemple de tas max est : Le tas max peut être construit à partir d'un tableau. Ce tableau sera pensé en termes d'arborescence. Pour un tas, si la racine (nœud parent supérieur de l'arbre) est stockée à la position (index) n, elle est définie pour le tableau, theArray , comme theArray[n]. Les nœuds enfants gauche et droit se trouvent donc respectivement dans theArray[2n+1] et theArray[2n+2] . Pour le tas max, la racine est à theArray[0] . Pour le niveau n, racine n = 0 : theArr[n] est le nœud parent theArr[(2*n)+1] est le nœud enfant gauche theArr[(2*n)+2] est le nœud enfant droit

La classe PriorityQueue

Les tas en Java peuvent être implémentés à l'aide de la classe PriorityQueue . Les PriorityQueues sont utilisées pour trouver l'élément le plus ou le moins important dans une collection. La classe PriorityQueue se trouve dans le java.util.package . PriorityQueues doit être formé d'objets comparables afin qu'ils soient placés dans un ordre particulier dans la file d'attente. PriorityQueue peut avoir un comparateur pour qu'une comparaison entre les objets soit faite et la file d'attente formée selon cette comparaison. Un exemple est :

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

Donner une sortie : Dans cet exemple, la taille par défaut de intQueue est 11, donc n'a pas été indiquée (généralement le premier argument avant le comparateur) et le comparateur a été donné comme suit : Cela fera une comparaison entre les éléments dans intQueue et le triera en longueurs de tableau par ordre croissant.

Implémentation de PriorityQueue pour créer un Max Heap

La classe PriorityQueue utilise par défaut le tas min sans comparateur. Le tas min est l'opposé du tas max et donc la racine est la plus petite valeur et les nœuds enfants successifs sont supérieurs ou égaux à la racine et aux nœuds parents suivants. Pour cette raison, pour le tas max, il est nécessaire d'utiliser reverseOrder() du framework Collections de Java comme comparateur. Cela garantira que nous obtenons un tas maximum et non un tas minimum. Cette classe a des méthodes utiles telles que add() , contains() , remove() , poll() et peek() . Les éléments sont ajoutés à la file d'attente et peuvent être dans n'importe quel ordre. La nouvelle file d'attente PriorityQueue stockera ces éléments sous forme de tas max dans l'ordre inverse. Lorsque la file d'attente est écrite, l'ordre sera : Racine Left-child avec root comme parent (Left-child_1) Right-child avec root comme parent (Right-child_1) Left-child avec Left-child_1 comme parent (Left-child_2 ) Enfant droit avec enfant gauche_1 comme parent (enfant droit_2) Enfant gauche avec enfant droit_1 comme parent (enfant gauche_3) Enfant droit avec enfant droit_1 comme parent (enfant droit_3) Enfant gauche avec enfant gauche_2 comme parent (Left-child_4) Right-child avec Left-child_2 comme parent (Right-child_4), etc.Le code suivant est un exemple de création d'un tas max (maxheap) en java. La première chose à faire est de remplir un tableau avec les valeurs pour lesquelles le tas max sera créé. C'est ce qu'on appelle leArray . Ensuite, une PriorityQueue , theQueue , est créée, puis les éléments de theArray y sont ajoutés. Cela utilise la méthode add() , par exemple theQueue.add(10) pour ajouter 10 à la fin de la file d'attente. Pour illustrer certaines des fonctionnalités de la classe PriorityQueue , la méthode peek() est ensuite utilisée pour trouver la tête du tas, et c'est la valeur maximale, dans ce cas, 99. La tâche suivante consiste à vérifier la taille du tas en utilisant la taille()qui s'avère être 9 et cela est imprimé sur la console. La méthode writeMaxHeap écrit les éléments dans la file d'attente dans l'ordre racine, enfant gauche avec racine comme parent, enfant droit avec racine comme parent, enfant gauche avec premier enfant gauche comme parent, enfant droit avec premier enfant gauche comme parent, enfant droit avec le premier enfant droit comme parent, enfant gauche avec le premier enfant droit comme parent, etc., avec les valeurs suivantes utilisant les enfants gauche et droit comme parents dans le même ordre que ci-dessus. La méthode PriorityQueue contains(J) est utilisée pour savoir si un élément spécifique, J, est dans une file d'attente. Dans ce cas, nous recherchons J = 10. Dans notre exemple, il est vrai que ceci est dans la file d'attente, donc cela est écrit sur la console comme vrai. Une autre méthode PriorityQueue , remove(J) est ensuite utilisée pour supprimer J = 10 de theQueue . Pour illustrer davantage la fonctionnalité de PriorityQueue , la méthode poll() est utilisée pour supprimer l'élément head (valeur maximale) à l'aide d'une boucle while , en supprimant à chaque fois l'élément head dans la nouvelle file d'attente et en diminuant la taille de la file d'attente d'un à chaque fois. Cela se produit dans la méthode writeQueueappelé depuis le principal. Chaque fois que l'élément supprimé est imprimé sur la console. La file d'attente d'origine n'aura finalement plus d'éléments. Les éléments imprimés sont le tas maximum par ordre décroissant de valeur, où la tête de la file d'attente est imprimée à chaque fois.

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

Sortir:

Max Heapifier

L'algorithme Max Heapify est utilisé pour s'assurer qu'un arbre binaire est un tas maximum. Si nous sommes à un nœud, n, et ses nœuds enfants, gauche et droite sont également des tas max eux-mêmes, alors super, nous avons un tas max. Si ce n'est pas le cas dans tout l'arbre, nous n'avons pas de tas maximum. L'algorithme Max Heapify est utilisé pour trier l'arbre afin qu'il respecte les principes de maxheap. Max Heapify fonctionne sur un seul nœud. Si l'exigence est que le tableau soit un tableau max heap, alors tous les sous-arbres doivent être convertis en maxheap avant la racine, un à la fois. L'algorithme doit être utilisé sur chaque nœud. Cela sera fait sur N/2 nœuds (les feuilles respecteront les exigences de tas max). La complexité temporelle du tas est O(NlogN), et pour un nœud à la hauteur X, la complexité temporelle est O(X). Le code suivant montre comment maxheapify un arbre (un tableau).

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

Donner une sortie : Dans ce code, theArray est créé et rempli de nombres. Un deuxième tableau, newArray , est créé et cette fois il contiendra le résultat de la méthode, maxheapCreate , le tableau max heap. La méthode maxHeapCreate est appelée depuis main , et ici un nouveau tableau, theNewArr , est créé et rempli avec les résultats maxHeapify . Cela se fait en bouclant sur la moitié de la taille du tableau d'entrée. Pour chaque passage de la boucle, la méthode maxHeapify , est appelée en commençant par l'élément au milieu du tableau et en terminant par le premier. Pour chaque appel de maxHeapify, l'enfant gauche et l'enfant droit du nœud parent, i, sont trouvés et des vérifications sont effectuées pour trouver lequel est le plus grand des trois, en le définissant comme maxVal . Si maxVal n'est pas égal au nœud parent alors un échange est effectué pour que le nœud parent et maxVal soient échangés puis maxHeapify est appelé à nouveau cette fois sur maxVal et les mêmes étapes sont effectuées comme précédemment. Finalement, le tas max sera créé et il n'y aura plus d'itérations à effectuer. Le tableau mis à jour, array , est maintenant renvoyé à main en tant que newArray , puis chaque élément consécutif est imprimé sur la console. nouveauTableauest maintenant un tas max. Notez que, comme dans l'exemple précédent utilisant PriorityQueue, les nombres sont écrits : racine, enfant droit de la racine en tant que parent, enfant gauche de la racine en tant que parent, enfant droit du premier enfant droit en tant que parent, enfant gauche du premier enfant gauche en tant que parent, enfant droit du premier enfant gauche en tant que parent, enfant gauche du premier enfant droit en tant que parent, etc. Ils sont dans un ordre légèrement différent de ceux lors de l'utilisation de PriorityQueue car la comparaison est effectuée entre des éléments consécutifs alors que dans l'exemple maxheapify, le nœud est comparé aux deux éléments successifs suivants du tableau et échangé pour la plus grande valeur. En bref, deux algorithmes différents sont utilisés. Les deux créent un tas maximum.

Conclusion

Nous avons donc examiné ici le tas maximum et comment il peut être créé avec un algorithme PriorityQueue ou Max Heapify. L'utilisation de PriorityQueue avec reverseOrder() est une manière astucieuse de le faire et la méthode recommandée. Cependant, vous pouvez étudier ces exemples et écrire vos propres méthodes car ce sera un bon exercice de codage qui vous aidera à réussir votre entretien pour Java Junior.