Implémenter le tas Min-Max en Java

1. Introduction à Min-Max Heap en Java
2. Implémenter Max-Heap avec la classe PriorityQueue et Collections.reverseOrder() en Java
3. Implémenter Min-Heap avec la classe PriorityQueue en Java

Cet article implémentera un tas max et un tas min en utilisant la classe PriorityQueue. Nous démontrerons également l’insertion et la suppression des éléments du tas.

Introduction à Min-Max Heap en Java

Un tas est une structure de données basée sur des arbres, et il forme un arbre binaire complet. Les tas sont représentés sous forme de tableau. Il existe deux types de tas : le tas minimum et le tas maximum. Le tas minimum, également connu sous le nom de tas min, a la plus petite valeur dans son nœud racine ou le nœud parent. De même, le tas max a la plus grande valeur dans le nœud racine ou le nœud parent. Par conséquent, la structure de données de tas facilite l’extraction du plus grand et du plus petit élément d’un tableau. Nous pouvons obtenir le plus grand et le plus petit élément dans O(1). La complexité pour supprimer ou insérer les éléments vers et depuis le tas est O(log N).

Un tas min-max est une structure de données qui contient une alternance de niveaux minimum et maximum. Le nœud racine contient la plus petite valeur et le niveau suivant en dessous représente la plus grande valeur. Les valeurs minimales sont représentées avec des niveaux pairs comme 0, 2, 4. Les niveaux impairs comme 1, 3, 5 représentent les valeurs maximales.

Implémenter Max-Heap avec la classe PriorityQueue et Collections.reverseOrder() en Java

Nous pouvons utiliser la classe PriorityQueue pour implémenter les tas en Java. La classe implémente le min-heap par défaut, et nous pouvons utiliser la méthode reverseOrder() de Collections pour implémenter le max-heap. Nous pouvons utiliser la méthode peek() pour afficher l’élément du nœud racine dans un tas. La méthode poll() renvoie et supprime la valeur au nœud racine. Nous pouvons utiliser la méthode contains() pour vérifier si un élément existe dans un tas.

Par exemple, importez tout depuis le package java.util. Créez une classe MaxHeap et écrivez la méthode principale. Créez ensuite une instance de la classe PriorityQueue en tant que pq. Utilisez le type générique pour créer l’instance Integer. Écrivez Collections.reverseOrder() dans la parenthèse lors de la création de l’objet. Utilisez la méthode add() pour ajouter quatre valeurs entières. Appelez la méthode peek() avec l’objet pq et imprimez-le. Ensuite, utilisez la méthode poll() sur l’objet. Ensuite, appelez la méthode remove() avec une valeur 30 comme paramètre puis imprimez les éléments du tableau en utilisant les méthodes iterator() et hasNext(). Enfin, utilisez la méthode contains() avec un paramètre 20.

Dans l’exemple ci-dessous, le import java.util.* importera la classe PriorityQueue, que nous avons utilisée pour créer un max-heap. Nous avons ajouté les valeurs 1, 2, 3 et 4 au tas. La méthode peek() a renvoyé la valeur 4, qui est la plus grande d’un tas. Ensuite, la méthode poll() a supprimé le nombre maximum, 4. Ensuite, nous avons utilisé la méthode remove() pour supprimer le nombre 3, et nous avons imprimé les éléments restants dans un tas. Il a imprimé les valeurs 1 et 2 comme nous avons déjà supprimé 3 et 4. Enfin, nous avons vérifié si le tas contient un nombre 2 en utilisant la méthode contains(). Il a renvoyé true car il existe le nombre dans un tas. Ainsi, nous avons implémenté le max-heap en utilisant la classe PriorityQueue avec l’utilisation de Collectios.reverseOrder().

Exemple de code :

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

Production:

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

Implémenter Min-Heap avec la classe PriorityQueue en Java

La classe PriorityQueue implémente le tas min par défaut. Nous appliquons la même méthode d’implémentation pour le tas min que pour le tas max. Nous utilisons les mêmes méthodes comme peek(), remove(), poll() et contains() pour effectuer les mêmes opérations.

Dans l’exemple ci-dessous, nous avons ajouté les nombres 1, 2, 3 et 4 dans un tas. La méthode peek() a renvoyé l’élément dans le nœud racine, qui est 1 comme indiqué dans la sortie. Nous avons utilisé la méthode poll() pour supprimer l’élément de nœud racine 1. Nous avons à nouveau supprimé la valeur 3 du tas avec la fonction remove(). Après avoir supprimé ces valeurs, notre tas ne contient que les éléments 2 et 4. Enfin, nous avons utilisé la méthode contains() pour vérifier si nous valorisons 3 dans un tas. Comme nous l’avons déjà supprimé, la méthode renvoie une valeur false. Ainsi, nous avons implémenté un min-heap en utilisant la classe PriorityQueue.

Exemple de code :

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

Production:

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false