Java Priority Queue : pas une file d'attente classique

Dans cet article, nous apprenons une file d'attente prioritaire, classe Java, qui implémente l'interface Queue. Que sait un programmeur de l'interface de file d'attente standard ? Tout d'abord, cette interface est basée sur le principe FIFO ou « first in first out ». Cela rappelle une file d'attente régulière dans son sens commun. Vous voulez prendre un café chez McDrive ? Si votre voiture est la première près de la fenêtre, vous prendrez votre café avant le conducteur qui est le suivant.

Déclaration d'interface de file d'attente

public interface Queue<E> extends Collection<E>

Qu'est-ce qu'une file d'attente prioritaire

Qu'est-ce qu'une file d'attente prioritaire ? Tout d'abord, c'est une classe qui implémente l'interface Queue en cas d'insertion d'un élément à l'arrière et de suppression d'un élément de la tête. Cependant, ce n'est pas une file d'attente habituelle à l'intérieur. L'ordre des éléments de la file d'attente prioritaire Java dépend de la priorité des éléments. L'élément avec la priorité la plus élevée sera déplacé vers la tête de la file d'attente. Si vous supprimez (servez) l'élément le mieux classé, le second va au chef chercher son café. Comment la priorité est-elle déterminée ? Selon la documentation, les éléments de la file d'attente prioritaire sont ordonnés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente, selon le constructeur utilisé. Une file d'attente prioritaire basée sur un tas min de priorité. Cela signifie que, dans le cas d'éléments de file d'attente de nombres, le premier élément de la file d'attente sera le minimum de ces nombres. Très souvent, après avoir lu cette définition, les étudiants débutants commencent à penser que la file d'attente prioritaire est triée de manière linéaire. Autrement dit, si, par exemple, nous utilisons une file d'attente dont les éléments sont des nombres naturels, le premier élément sera le plus petit et le dernier - le plus grand. Ce n'est pas tout à fait vrai. Pour comprendre comment la file d'attente prioritaire fonctionne réellement et ce qu'elle donne, vous devez comprendre comment fonctionne le tas. Nous considérons la structure interne de la file d'attente prioritaire en utilisant un exemple un peu plus loin. Arrêtons-nous maintenant sur ses attributs externes. alors le premier élément sera le plus petit et le dernier - le plus grand. Ce n'est pas tout à fait vrai. Pour comprendre comment la file d'attente prioritaire fonctionne réellement et ce qu'elle donne, vous devez comprendre comment fonctionne le tas. Nous considérons la structure interne de la file d'attente prioritaire en utilisant un exemple un peu plus loin. Arrêtons-nous maintenant sur ses attributs externes. alors le premier élément sera le plus petit et le dernier - le plus grand. Ce n'est pas tout à fait vrai. Pour comprendre comment la file d'attente prioritaire fonctionne réellement et ce qu'elle donne, vous devez comprendre comment fonctionne le tas. Nous considérons la structure interne de la file d'attente prioritaire en utilisant un exemple un peu plus loin. Arrêtons-nous maintenant sur ses attributs externes.

Constructeurs et déclaration de la classe PriorityQueue

La classe PriorityQueue fournit 6 façons différentes de construire une file d'attente prioritaire en Java.

• PriorityQueue() - file d'attente vide avec la capacité initiale par défaut (11) qui ordonne ses éléments en fonction de leur ordre naturel.
• PriorityQueue(Collection c) - file d'attente vide contenant les éléments de la collection spécifiée.
• PriorityQueue(int initialCapacity) - file d'attente vide avec la capacité initiale spécifiée qui ordonne ses éléments en fonction de leur ordre naturel.
• PriorityQueue(int initialCapacity, Comparator comparator) - file d'attente vide avec la capacité initiale spécifiée qui ordonne ses éléments en fonction du comparateur spécifié.
• PriorityQueue(PriorityQueue c) - file d'attente vide contenant les éléments de la file d'attente prioritaire spécifiée.
• PriorityQueue(SortedSet c) - file d'attente vide contenant les éléments du jeu trié spécifié.

La file d'attente prioritaire en Java est déclarée de la manière suivante :

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Création d'une file d'attente prioritaire

Créons une file d'attente prioritaire d'entiers. Implémentation de la file d'attente prioritaire, code Java :

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Nous avons créé une file d'attente prioritaire sans arguments. Dans ce cas, la tête de la file d'attente prioritaire est le numéro minimal de la file d'attente. Si vous enlevez la tête, le prochain plus petit élément prendra cette place. Ainsi, vous pouvez supprimer des éléments de la file d'attente dans l'ordre croissant. Si nécessaire, vous pouvez modifier le principe de commande à l'aide de l'interface Comparator.

Méthodes Java PriorityQueue

La classe Java PriorityQueue a des méthodes importantes pour ajouter, supprimer et vérifier des éléments.

Insérer des éléments dans la file d'attente prioritaire

• boolean add(object) insère l'élément spécifié dans la file d'attente prioritaire. Renvoie true en cas de succès. Si la file d'attente est pleine, la méthode lève une exception.
• booléen offre(objet) insère l'élément spécifié dans cette file d'attente prioritaire. Si la file d'attente est pleine, la méthode renvoie false.

Vous pouvez utiliser les deux opérations d'addition, il n'y a pas de différences pour les cas majoritaires. Voici un petit exemple d'initiation et d'ajout d'éléments dans la file prioritaire.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

La sortie est :

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

L'ordre des éléments semble bizarre, nous l'expliquerons plus tard.

Récupération et suppression d'éléments de la file d'attente prioritaire

• boolean remove(object) supprime une seule instance de l'élément spécifié de cette file d'attente, si elle est présente.
• L'objet poll() récupère et supprime la tête de cette file d'attente. Renvoie null si la file d'attente est vide.
• void clear() supprime tous les éléments de la file d'attente prioritaire.
• L'objet element() récupère la tête de cette file d'attente sans la supprimer. Lève NoSuchElementException si la file d'attente est vide.
• Object peek() récupère la tête de la file d'attente sans la supprimer. Renvoie null si la file d'attente est vide.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Le résultat:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Comme vous pouvez le voir, essayer d'imprimer la tête de la file d'attente vide à l'aide de la méthode element() conduit à NoSuchElementexception .

Comparateur PriorityQueue

• Comparator comparator() renvoie le comparateur utilisé pour classer les éléments dans la file d'attente. Renvoie null si la file d'attente est triée selon l'ordre naturel de ses éléments.

File d'attente prioritaire Java, exemple avec comparateur

Nous avons utilisé l'ordre naturel (ascendant) dans les exemples de code ci-dessus, mais nous devons parfois le modifier. Voici un exemple de file d'attente prioritaire Java, où nous créons notre propre classe de comparateur interne qui implémente l'interface Comparator. Notre comparateur triera les éléments du plus grand au plus petit.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Le résultat:

the head of Queue = 5
5
4
3
2
1

La tête de la file d'attente n'est plus l'élément minimal, mais maximal, et l'ordre a été changé en inversé.

Itération sur PriorityQueue à l'aide de l'itérateur

ProrityQueue fait partie du framework Collection et implémente l' interface Iterable<> . Pour parcourir les éléments d'une file d'attente prioritaire, vous pouvez utiliser la méthode iterator() . Voici un exemple:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Le résultat:

1 2 4 5 3 

Plus de méthodes PriorityQueue

• boolean contains(Object o) renvoie vrai si la file d'attente contient l'élément o.
• int size() renvoie le nombre d'éléments dans cette file d'attente.
• Object[] toArray() renvoie un tableau contenant tous les éléments de cette file d'attente.

Voici un exemple:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Le résultat:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Définition de PriorityQueue Java 8

Si vous ouvrez la documentation de priorityqueue java 8, vous y trouverez la définition suivante : Une file d'attente prioritaire illimitée basée sur un tas prioritaire. Les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente, selon le constructeur utilisé. Une file d'attente prioritaire n'autorise pas les éléments nuls. Une file d'attente prioritaire reposant sur l'ordre naturel ne permet pas non plus l'insertion d'objets non comparables (cela peut entraîner ClassCastException). Heap est un mot très important ici. Il explique les propriétés de l'ordre des éléments de la file d'attente prioritaire.

Le principe du travail PriorityQueue : Binary Heap

Commençons par un exemple. Créons deux objets implémentant l'interface Queue. L'un d'eux LinkedList, le second — PriorityQueue. Les deux ont 5 éléments d'Integer (1,2,3,4 et 5) et nous commençons à mettre les éléments dans nos files d'attente du plus grand au plus petit. Ainsi, le premier vient 5, puis 4, 3, 2 et le dernier sera 1. Ensuite, imprimez les deux listes pour vérifier la commande.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Le résultat de ces travaux de code est le suivant :

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Eh bien, l'ordre des listes liées est prévisible et compréhensible. Il est ordonné selon le principe FIFO. Nous avons commencé avec 5, donc cet élément est le tout premier en ligne, puis passe à 4 et ainsi de suite. Que pouvons-nous dire sur l'ordre de la file d'attente prioritaire ? Docs a déclaré que les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente. Cependant cet ordre ne semble pas « naturel » au sens du tri linéaire. Nous attendons plutôt [1, 2, 3, 4, 5], pas [1, 2, 4, 5, 3]. Pour comprendre pourquoi l'ordre de récupération est tel qu'il est, rappelons cette file d'attente prioritaire basée sur un tas. Quel est le tas? C'est une structure de données basée sur un arbre binaire. La principale propriété du tas : la priorité de chaque parent est supérieure aux priorités de ses enfants. Je vous rappelle qu'un arbre est appelé un binaire complet si chaque parent n'a pas plus de deux enfants, et le remplissage des niveaux va de haut en bas (à partir du même niveau — de gauche à droite). Le tas binaire se réorganise à chaque fois que des éléments y sont ajoutés ou supprimés. En cas de min-heap, le plus petit élément va à la racine quel que soit l'ordre de son insertion. File d'attente prioritaire basée sur ce segment minimal. Cela signifie qu'en cas d'éléments de file d'attente de nombres, le premier élément de la file d'attente sera le minimum de ces nombres. Si vous supprimez la racine, la plus petite suivante devient une racine.

Revenons à notre exemple.

Étape 1. Nous mettons '5' dans la file d'attente prioritaire. Cela devient une racine. Étape 2. Nous ajoutons '4' dans la file d'attente prioritaire. 4 <5, donc le nouvel élément doit être supérieur à l'ancien. Le 4 devient une racine, 5 est son enfant gauche. Maintenant, la structure de données en Java est [4, 5] Étape 3. Nous ajoutons '3'. Il devient temporairement un enfant droit d'une racine (4). Cependant, 3 < 4, nous devrions donc le relever. Échangez 3 et 4. Nous avons maintenant une structure telle que [3, 5, 4] Étape 4. Nous ajoutons '2'. Cela devient un enfant gauche de 5. 2<5, alors échangez-les. 2 devient un enfant gauche de 3, 2 < 3, donc encore un processus d'échange. Nous avons maintenant une structure [2,3,4,5] Étape 5.Nous ajoutons '1'. Il vient de l'enfant droit du 3 à l'enfant gauche du 2, puis va à la racine. La structure de données du résultat : [1,2,4,5,3] Le processus de suppression part d'une racine et provoque les procédures inverses. Donc, nous avons d'abord 1 comme racine, puis 2, 3, 4 et enfin 5. C'est pourquoi l'utilisation de la suppression de l'opération poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

nous avons "trié" en sortie de sens linéaire :

1
2
3
4
5

Ainsi, la file d'attente prioritaire pourrait être efficace pour certaines opérations. Il faut O(log N) pour insérer et supprimer chaque élément, et vous pouvez obtenir l'élément minimal dans O(1). Voici l'exemple complet :

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Il est important de comprendre que les files d'attente prioritaires sont basées sur des tas binaires, elles ne conservent donc pas les éléments dans un ordre de tri linéaire. Chaque chemin de la racine à la feuille est ordonné, mais les différents chemins de la racine ne le sont pas. Cela signifie que vous pouvez obtenir très rapidement l'élément minimal de la file d'attente.

Ce que vous devez savoir sur la file d'attente prioritaire. Brève liste

• La file d'attente prioritaire n'autorise pas les objets NULL.
• Vous ne pouvez ajouter que des objets comparables dans PriorityQueue.
• La file d'attente prioritaire est construite comme un tas min, une sorte d'arbre binaire. L'élément minimal est une racine. Les objets de la file d'attente prioritaire sont classés par défaut dans l'ordre naturel.
• Vous pouvez utiliser Comparator si vous avez besoin d'une commande personnalisée.
• PriorityQueue n'est pas thread-safe, il est donc préférable d'utiliser PriorityBlockingQueue pour travailler dans un environnement concurrent.
• PriorityQueue fournit un temps O(log(n)) pour les méthodes d'ajout et d'interrogation et O(1) pour obtenir un minimum d'éléments.