Une PriorityQueue est utilisée lorsque les objets sont censés être traités en fonction de la priorité. On sait qu'un File d'attente suit l'algorithme First-In-First-Out, mais parfois les éléments de la file d'attente doivent être traités en fonction de la priorité, c'est alors que la PriorityQueue entre en jeu.
PriorityQueue est basé sur le tas prioritaire. Les éléments de la file d'attente prioritaire sont ordonnés selon l'ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente, selon le constructeur utilisé.
Dans la file d'attente prioritaire ci-dessous, un élément avec une valeur ASCII maximale aura la priorité la plus élevée.
Déclaration:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
La classe implémente Sérialisable , Itérable , Collection , File d'attente interfaces.
Quelques points importants sur la file d'attente prioritaire sont les suivants:
- PriorityQueue n'autorise pas null.
- Nous ne pouvons pas créer une PriorityQueue d'objets non comparables
- PriorityQueue sont des files d'attente non liées.
- La tête de cette file d'attente est le moindre élément par rapport à l'ordre spécifié. Si plusieurs éléments sont à égalité pour la moindre valeur, la tête est l’un de ces éléments – les égalités sont rompues arbitrairement.
- Étant donné que PriorityQueue n'est pas thread-safe, Java fournit la classe PriorityBlockingQueue qui implémente l'interface BlockingQueue à utiliser dans un environnement multithread Java.
- Les opérations de récupération de file d'attente interrogent, suppriment, jettent un coup d'oeil et l'élément accède à l'élément en tête de la file d'attente.
- Il fournit un temps O(log(n)) pour les méthodes d'ajout et d'interrogation.
- Il hérite des méthodes de File d'attente abstraite , Collection abstraite , Collection, et Objet classe.
Constructeurs :
1. PriorityQueue() : Crée une PriorityQueue avec la capacité initiale par défaut (11) qui classe ses éléments selon leur ordre naturel.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (Collection c) : Crée un PriorityQueue contenant les éléments de la collection spécifiée.
PriorityQueue pq = new PriorityQueue (Collection c);
3. PriorityQueue (int initialCapacity) : crée une PriorityQueue avec la capacité initiale spécifiée qui classe ses éléments selon leur ordre naturel.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue (int initialCapacity, Comparateur comparateur) : Crée un PriorityQueue avec la capacité initiale spécifiée qui classe ses éléments en fonction du comparateur spécifié.
PriorityQueue pq = new PriorityQueue (int initialCapacity, Comparator comparator);
5. PriorityQueue (PriorityQueue c) : Crée une PriorityQueue contenant les éléments dans la file d'attente prioritaire spécifiée.
PriorityQueue pq = new PriorityQueue (PriorityQueue c);
6. PriorityQueue (SortedSetc) : Crée une PriorityQueue contenant les éléments de l'ensemble trié spécifié.
PriorityQueue pq = new PriorityQueue (SortedSet c);
7. PriorityQueue (Comparateur comparateur) : Crée un PriorityQueue avec la capacité initiale par défaut et dont les éléments sont ordonnés selon le comparateur spécifié.
PriorityQueue pq = new PriorityQueue (Comparateur c);
Exemple:
L'exemple ci-dessous explique les opérations de base suivantes de la file d'attente prioritaire.
tri par insertion en Java
- boolean add(E element) : Cette méthode insère l'élément spécifié dans cette file d'attente prioritaire.
- public peek() : Cette méthode récupère, mais ne supprime pas, la tête de cette file d'attente, ou renvoie null si cette file d'attente est vide.
- public poll() : Cette méthode récupère et supprime la tête de cette file d'attente, ou renvoie null si cette file d'attente est vide.
Java
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>Sortir
10 10 15>
Opérations sur PriorityQueue
Voyons comment effectuer quelques opérations fréquemment utilisées sur la classe Priority Queue.
1. Ajout d'éléments : Afin d'ajouter un élément dans une file d'attente prioritaire, nous pouvons utiliser la méthode add(). L'ordre d'insertion n'est pas conservé dans PriorityQueue. Les éléments sont stockés selon l'ordre de priorité qui est croissant par défaut.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Sortir
[0, 1, 1, 1, 2, 1]>
Nous n'obtiendrons pas d'éléments triés en imprimant PriorityQueue.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Sortir
[For, Geeks, Geeks]>
2. Suppression d'éléments : Afin de supprimer un élément d’une file d’attente prioritaire, nous pouvons utiliser la méthode remove(). S'il existe plusieurs objets de ce type, la première occurrence de l'objet est supprimée. En dehors de cela, la méthode poll() est également utilisée pour supprimer la tête et la renvoyer.
Java
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>Sortir
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Accéder aux éléments : Puisque Queue suit le principe First In First Out, nous ne pouvons accéder qu’à la tête de la file d’attente. Pour accéder aux éléments d'une file d'attente prioritaire, nous pouvons utiliser la méthode peek().
Java
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>Sortir
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Itération de la PriorityQueue : Il existe plusieurs façons de parcourir PriorityQueue. La méthode la plus connue consiste à convertir la file d'attente en tableau et à la parcourir à l'aide de la boucle for. Cependant, la file d'attente dispose également d'un itérateur intégré qui peut être utilisé pour parcourir la file d'attente.
Java
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>Sortir
For Geeks Geeks>
Exemple:
Java
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Sortir
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Exemples en temps réel :
La file d'attente prioritaire est une structure de données dans laquelle les éléments sont classés par priorité, les éléments les plus prioritaires apparaissant au début de la file d'attente. Voici quelques exemples concrets d’utilisation des files d’attente prioritaires :
- Planification des tâches : dans les systèmes d'exploitation, les files d'attente prioritaires sont utilisées pour planifier les tâches en fonction de leurs niveaux de priorité. Par exemple, une tâche hautement prioritaire telle qu'une mise à jour critique du système peut être planifiée avant une tâche moins prioritaire telle qu'un processus de sauvegarde en arrière-plan. Salle d'urgence : Dans la salle d'urgence d'un hôpital, les patients sont triés en fonction de la gravité de leur état, ceux qui sont dans un état critique étant traités en premier. Une file d'attente prioritaire peut être utilisée pour gérer l'ordre dans lequel les patients sont vus par les médecins et les infirmières. Routage réseau : Dans les réseaux informatiques, les files d'attente prioritaires sont utilisées pour gérer le flux des paquets de données. Les paquets hautement prioritaires tels que les données vocales et vidéo peuvent avoir la priorité sur les données moins prioritaires telles que les e-mails et les transferts de fichiers. Transport : Dans les systèmes de gestion du trafic, les files d'attente prioritaires peuvent être utilisées pour gérer le flux du trafic. Par exemple, les véhicules d’urgence comme les ambulances peuvent avoir la priorité sur les autres véhicules afin de garantir qu’ils puissent atteindre rapidement leur destination. Planification des tâches : dans les systèmes de planification des tâches, les files d'attente prioritaires peuvent être utilisées pour gérer l'ordre dans lequel les tâches sont exécutées. Les tâches hautement prioritaires telles que les mises à jour critiques du système peuvent être planifiées avant les tâches moins prioritaires telles que les sauvegardes de données. Marchés en ligne : sur les marchés en ligne, les files d'attente prioritaires peuvent être utilisées pour gérer la livraison des produits aux clients. Les commandes hautement prioritaires telles que l’expédition express peuvent avoir la priorité sur les commandes d’expédition standard.
Dans l'ensemble, les files d'attente prioritaires constituent une structure de données utile pour gérer les tâches et les ressources en fonction de leurs niveaux de priorité dans divers scénarios du monde réel.
Méthodes dans la classe PriorityQueue
| MÉTHODE | DESCRIPTION |
|---|---|
| ajouter(Et et) | Insère l'élément spécifié dans cette file d'attente prioritaire. |
| clair() | Supprime tous les éléments de cette file d'attente prioritaire. |
| comparateur() | Renvoie le comparateur utilisé pour trier les éléments de cette file d'attente, ou null si cette file d'attente est triée selon l'ordre naturel de ses éléments. |
| contient ?(Objet o) | Renvoie vrai si cette file d'attente contient l'élément spécifié. |
| forEach ? (Action du consommateur) | Exécute l'action donnée pour chaque élément de l'Iterable jusqu'à ce que tous les éléments aient été traités ou que l'action lève une exception. |
| itérateur() | Renvoie un itérateur sur les éléments de cette file d'attente. |
| offre ?(E e) | Insère l'élément spécifié dans cette file d'attente prioritaire. |
| supprimer ?(Objet o) | Supprime une seule instance de l'élément spécifié de cette file d'attente, si elle est présente. |
| supprimerTout ?(Collection c) | Supprime tous les éléments de cette collection qui sont également contenus dans la collection spécifiée (opération facultative). |
| RemoveIf? (Filtre de prédicat) | Supprime tous les éléments de cette collection qui satisfont au prédicat donné. |
| retenirTout ?(Collection c) | Conserve uniquement les éléments de cette collection qui sont contenus dans la collection spécifiée (opération facultative). |
| séparateur() | Crée un Spliterator à liaison tardive et à échec rapide sur les éléments de cette file d'attente. |
| versArray() | Renvoie un tableau contenant tous les éléments de cette file d'attente. |
| versArray?(T[] a) | Renvoie un tableau contenant tous les éléments de cette file d'attente ; le type d'exécution du tableau renvoyé est celui du tableau spécifié. |
Méthodes déclarées dans la classe java.util.AbstractQueue
| MÉTHODE | DESCRIPTION |
|---|---|
| ajouterTout(Collection c) | Ajoute tous les éléments de la collection spécifiée à cette file d'attente. |
| élément() | Récupère, mais ne supprime pas, la tête de cette file d'attente. |
| retirer() | Récupère et supprime la tête de cette file d'attente. |
Méthodes déclarées dans la classe java.util.AbstractCollection
| MÉTHODE | DESCRIPTION |
|---|---|
| contientTout(Collection c) | Renvoie vrai si cette collection contient tous les éléments de la collection spécifiée. |
| est vide() | Renvoie vrai si cette collection ne contient aucun élément. |
| àChaîne() | Renvoie une représentation sous forme de chaîne de cette collection. |
Méthodes déclarées dans l'interface java.util.Collection
| MÉTHODE | DESCRIPTION |
|---|---|
| contientTout(Collection c) | Renvoie vrai si cette collection contient tous les éléments de la collection spécifiée. |
| est égal à (Objet o) | Compare l'objet spécifié avec cette collection pour vérifier l'égalité. |
| code de hachage() | Renvoie la valeur du code de hachage pour cette collection. |
| est vide() | Renvoie vrai si cette collection ne contient aucun élément. |
| parallèleStream() | Renvoie un Stream éventuellement parallèle avec cette collection comme source. |
| taille() | Renvoie le nombre d'éléments dans cette collection. |
| flux() | Renvoie un Stream séquentiel avec cette collection comme source. |
| toArray (générateur de IntFunction) | Renvoie un tableau contenant tous les éléments de cette collection, en utilisant la fonction génératrice fournie pour allouer le tableau renvoyé. |
Méthodes déclarées dans l'interface java.util.Queue
| MÉTHODE | DESCRIPTION |
|---|---|
| coup d'oeil() | Récupère, mais ne supprime pas, la tête de cette file d'attente, ou renvoie null si cette file d'attente est vide. |
| sondage() | Récupère et supprime la tête de cette file d'attente, ou renvoie null si cette file d'attente est vide. |
Applications :
- Implémentation des algorithmes de Dijkstra et Prim.
- Maximiser la somme du tableau après K négations
Articles Liés :
classe vs objet en Java
- Classe Java.util.PriorityQueue en Java
- Implémenter PriorityQueue via Comparator en Java