Implémenter min-heap en Java

1. Implémentation de Min Heap sans utiliser de bibliothèque en Java
2. Implémentation de Min-Heap à l’aide de PriorityQueue en Java

Un Min Heap est un Heap dans lequel chaque nœud interne est inférieur ou égal aux valeurs de ses enfants. Nous verrons comment implémenter Min Heap avec et sans bibliothèque dans les points suivants.

Implémentation de Min Heap sans utiliser de bibliothèque en Java

Dans cet exemple, nous voyons l’implémentation sans utiliser de bibliothèque. Ici on crée une classe JavaMinHeap dans laquelle on crée trois variables d’instance HeapArray est un tableau de type int qui va garder toutes les valeurs du tas, size est la taille du tas, maxSize stocke le taille maximale du HeapArray. On crée aussi une variable statique FRONT de type int et on l’initialise à 1.

Nous obtenons maxSize en paramètre dans le constructeur et le stockons dans la variable d’instance maxSize. On initialise size avec 0 et HeapArray avec un tableau de int avec la taille de maxSize + 1. Nous stockons la valeur minimale de Integer au premier index de HeapArray.

Nous créons maintenant des méthodes pour effectuer des opérations sur le tas. La fonction parent() prend une position en paramètre et renvoie le parent de la position passée du nœud. Puis on crée leftChild() qui renvoie le fils gauche de la position reçue en paramètre. Il en va de même pour le bon enfant en utilisant rightChild() qui renvoie la valeur du nœud (2 * position) + 1.

isLeaf() vérifie si un nœud est un nœud feuille ou non, ce qui signifie qu’il a un enfant. swapNodes() est une méthode qui échange la valeur du nœud de la position fpos avec la position spos. Dans la méthode, nous créons une variable temp et l’initialisons, la position fpos de HeapArray et stockons la valeur spos de HeapArray dans HeapArray[fpos]. Maintenant, nous stockons la valeur temp dans HeapArray[spos].

convertToMinHeap() vérifie si la position reçue en paramètre est une feuille ou n’utilise pas isLeaf et sinon, vérifie si la valeur actuelle à la position de HeapArray est supérieure à l’enfant gauche ou droit. Ensuite, nous vérifions si l’enfant de gauche est plus petit que l’enfant de droite, et si c’est le cas, nous utilisons swapNodes() pour échanger les nœuds et passer la position et l’enfant de gauche à position. Nous convertissons à nouveau l’enfant gauche reçu en tas min en utilisant convertToMinHeap().

Nous utilisons insert() pour insérer les valeurs dans le tas min. Dans insert() nous retournons sans insérer si le tableau atteint maxSize ; sinon, nous obtenons la position à ++size et insérons l’élément reçu à HeapArray[++size]. Nous mettons size à current. Nous créons une boucle et échangeons les nœuds si l’élément à la position current est plus petit que son parent.

Pour imprimer le min-heap, nous créons printheap() et parcourons le HeapArray où le parent est à la ième position, l’enfant de gauche est à la position 2 * i et l’enfant de droite est à la position 2 * i + 1. Dans la fonction main(), nous utilisons insert() pour insérer des éléments dans le tas.

public class JavaMinHeap {
  private final int[] HeapArray;
  private int size;
  private final int maxsize;

  private static final int FRONT = 1;

  public JavaMinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    HeapArray = new int[this.maxsize + 1];
    HeapArray[0] = Integer.MIN_VALUE;
  }

  private int parent(int position) {
    return position / 2;
  }

  private int leftChild(int position) {
    return (2 * position);
  }

  private int rightChild(int position) {
    return (2 * position) + 1;
  }

  private boolean isLeaf(int position) {
    if (position >= (size / 2) && position <= size) {
      return true;
    }
    return false;
  }

  private void swapNodes(int fpos, int spos) {
    int temp;
    temp = HeapArray[fpos];
    HeapArray[fpos] = HeapArray[spos];
    HeapArray[spos] = temp;
  }

  private void convertToMinHeap(int position) {
    if (!isLeaf(position)) {
      if (HeapArray[position] > HeapArray[leftChild(position)]
          || HeapArray[position] > HeapArray[rightChild(position)]) {
        if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
          swapNodes(position, leftChild(position));
          convertToMinHeap(leftChild(position));
        } else {
          swapNodes(position, rightChild(position));
          convertToMinHeap(rightChild(position));
        }
      }
    }
  }

  public void insert(int element) {
    if (size >= maxsize) {
      return;
    }
    HeapArray[++size] = element;
    int current = size;

    while (HeapArray[current] < HeapArray[parent(current)]) {
      swapNodes(current, parent(current));
      current = parent(current);
    }
  }

  public void printHeap() {
    for (int i = 1; i <= size / 2; i++) {
      System.out.println("PARENT : " + HeapArray[i]);

      System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);

      System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
      System.out.println();
    }
  }

  public static void main(String[] arg) {
    System.out.println("The Min Heap is ");
    JavaMinHeap minHeap = new JavaMinHeap(10);
    minHeap.insert(10);
    minHeap.insert(2);
    minHeap.insert(7);
    minHeap.insert(15);
    minHeap.insert(90);
    minHeap.insert(19);
    minHeap.insert(8);
    minHeap.insert(22);
    minHeap.insert(9);

    minHeap.printHeap();
  }
}

Production:

The Min Heap is 
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7

PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90

PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8

PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15

Implémentation de Min-Heap à l’aide de PriorityQueue en Java

Dans ce programme, nous utilisons PriorityQueue qui est utilisé pour créer des tas max et min. PriorityQueue fournit plusieurs comme add() qui insère l’élément dans la file d’attente, peek() récupère la tête de la file d’attente et le supprime, poll() récupère également la tête de la file d’attente mais sans le supprimer . contains() vérifie que l’élément spécifié est la file d’attente. remove() supprime l’élément spécifié.

Nous combinons toutes les fonctions de PriorityQueue pour créer et effectuer des opérations min-heap. Nous créons d’abord un objet PriorityQueue vide de type Integer en utilisant new PriorityQueue(). Ensuite, nous ajoutons nos éléments à l’aide de la méthode add(). Pour imprimer et supprimer la tête de file d’attente, nous appelons priorityQueue.peek() qui affiche 10. Ensuite, nous imprimons tous les éléments de la file d’attente en utilisant for amélioré. Nous appelons maintenant poll() qui imprime et supprime 10. Ensuite, nous supprimons un élément de la file d’attente. Nous utilisons contains() qui renvoie un booléen pour vérifier si un élément est dans la file d’attente. Enfin, pour imprimer la valeur restante, nous convertissons la file d’attente en un tableau en utilisant toArray().

import java.util.*;

public class JavaMinHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(10);
    priorityQueue.add(15);
    priorityQueue.add(25);
    priorityQueue.add(200);

    System.out.println("The head value using peek(): " + priorityQueue.peek());

    System.out.println("The queue elements: ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.poll();
    System.out.println("After removing the head element using poll(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.remove(25);
    System.out.println("After removing 25 with remove(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    boolean b = priorityQueue.contains(15);
    System.out.println("Check if priorityQueue contains 15 using contains():  " + b);

    Object[] arr = priorityQueue.toArray();
    System.out.println("Values in array: ");
    for (Object o : arr) System.out.println("Value: " + o.toString());
  }
}

Production:

The head value using peek(): 10
The queue elements: 
10
15
25
200
After removing the head element using poll(): 
15
200
25
After removing 25 with remove(): 
15
200
Check if priorityQueue contains 15 using contains():  true
Values in array: 
Value: 15
Value: 200