java priority queue tutorial implementation examples
Ce didacticiel explique la file d'attente de priorité Java et les concepts associés tels que Comparator, Min et Max Priority Queue, ainsi que son implémentation avec des exemples:
La structure de données de file d'attente prioritaire est une file d'attente spéciale dans laquelle les éléments ne sont pas présents selon l'ordre FIFO, mais selon les éléments naturels ou tout comparateur personnalisé utilisé lors de la création de la file d'attente.
=> Jetez un œil au guide du débutant Java ici.
Ce que vous apprendrez:
File d'attente prioritaire en Java
Dans la file d'attente prioritaire, l'avant de la file d'attente a le moins d'éléments selon l'ordre naturel et l'arrière est pointé vers le plus grand élément de la file d'attente.
Un exemple de file d'attente prioritaire composée de nombres est illustré ci-dessous.
programmes d'entrevue java et réponses pour expérimentés
Ainsi, lorsqu'un élément est supprimé de la file d'attente prioritaire illustrée ci-dessus, ce sera le moindre élément.
De même, pour une file d'attente de priorité alphabétique, les valeurs ASCII seront prises en compte et les éléments de la file d'attente seront classés selon les valeurs ASCII.
Voici quelques-unes des principales caractéristiques de PriorityQueue:
- PriorityQueue est une file d'attente indépendante.
- PriorityQueue n'autorise pas les valeurs nulles.
- Pour les objets non comparables, nous ne pouvons pas créer de file d'attente prioritaire.
- PriorityQueue hérite des classes telles que AbstractQueue, AbstractCollection, Collection et Object.
- La tête ou l'avant de la file d'attente contient le moindre élément selon l'ordre naturel.
- L'implémentation de la file d'attente prioritaire n'est pas thread-safe. Ainsi, si nous souhaitons un accès synchronisé, nous devons utiliser PriorityBlockingQueue.
La classe PriorityQueue hérite de l'interface Java Queue et fait partie du package java.util.
La déclaration générale de la classe PriorityQueue est donnée ci-dessous:
public class PriorityQueue extends AbstractQueue implements SerializableLe diagramme ci-dessous montre la hiérarchie des classes pour la classe PriorityQueue.
Complexité temporelle de la file d'attente prioritaire
- La complexité temporelle de la file d'attente prioritaire pour les méthodes d'insertion (mise en file d'attente) et de suppression (retrait de la file d'attente) est O (log (n)).
- La file d'attente prioritaire a une complexité temporelle linéaire pour supprimer et contient des méthodes.
- Les méthodes qui récupèrent les éléments de la file d'attente prioritaire ont une complexité temporelle constante.
Exemple de file d'attente prioritaire en Java
Le programme ci-dessous montre une simple PriorityQueue en Java. Nous créons un objet de la classe PriorityQueue, y ajoutons des valeurs, puis affichons le contenu de la file d'attente à l'aide d'itérateur.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Production:
Méthodes API Java Priority Queue
Constructeurs:
| Prototype de constructeur | La description | |
|---|---|---|
| coup d'oeil | E coup d'oeil () | Renvoie la tête de la file d'attente sans supprimer l'élément. |
| File d'attente de priorité () | Un constructeur par défaut qui crée un objet PriorityQueue avec une capacité initiale de 1. | |
| PriorityQueue (collection c) | Crée un objet PriorityQueue avec les éléments initiaux de la collection donnée c. | |
| PriorityQueue (int initialCapacity) | Crée un objet PriorityQueue avec la ‘initialCapacity’ donnée. Les éléments sont classés selon l'ordre naturel. | |
| PriorityQueue (int initialCapacity, comparateur de comparaison) | Crée un objet PriorityQueue avec la ‘initialCapacity’ donnée. Les éléments sont classés en fonction du comparateur donné. | |
| PriorityQueue (PriorityQueue c) | Crée un objet PriorityQueue à partir d'un autre objet PriorityQueue donné par c. | |
| PriorityQueue (SortedSet c) | Crée un objet PriorityQueue à partir d'un SortedSet donné par c. |
Méthodes
| Méthode | Prototype de méthode | La description |
|---|---|---|
| ajouter | booléen ajouter (E e) | Ajoute l'élément e à PriorityQueue. |
| dégager | vide clair () | Efface la PriorityQueue en supprimant tous les éléments. |
| comparateur | Comparateur comparateur () | Renvoie un comparateur personnalisé utilisé pour l'ordre des éléments dans la file d'attente. |
| contient | boolean contient (Object o) | Vérifie si PriorityQueue contient l'élément o donné. Renvoie vrai si oui. |
| itérateur | Itérateur () | Méthode pour obtenir un itérateur pour la PriorityQueue donnée. |
| offre | offre booléenne (E e) | Insérez l'élément e donné dans PriorityQueue. |
| sondage | Sondage E () | Supprime et renvoie la tête de la file d'attente. Renvoie null si la file d'attente est vide. |
| supprimer | boolean remove (objet o) | Supprime une instance d'un élément donné o s'il est présent dans la file d'attente. |
| Taille | taille int () | Renvoie la taille ou le nombre d'éléments dans cette PriorityQueue. |
| toArray | Object () toArray () | Renvoie une représentation sous forme de tableau de la PriorityQueue donnée. |
| toArray | T () toArray (T () a) | Renvoie une représentation de tableau pour la file d'attente prioritaire donnée avec le même type d'exécution que le tableau spécifié a. |
Implémentation en Java
Voyons les méthodes ci-dessus de PriorityQueue à l’aide d’un programme Java.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Production:
comment ouvrir le fichier json sous windows
File d'attente prioritaire dans Java 8
Java 8 ajoute une méthode supplémentaire à la classe PriorityQueue, à savoir «spliterator ()».
Les détails de cette méthode sont donnés ci-dessous.
Nom de la méthode: séparateur
Prototype de méthode: spliterator final public ()
Description de la méthode: Cette méthode crée un séparateur sur les éléments PriorityQueue. Ce séparateur est à liaison tardive et rapide.
Comparateur de file d'attente prioritaire
Comme déjà mentionné, les éléments PriorityQueue sont naturellement ordonnés. Si nous voulons changer l'ordre, nous devons spécifier un comparateur et l'utiliser lors de la création de l'objet PriorityQueue. La PriorityQueue utilise ensuite ce comparateur pour ordonner ses éléments.
Le programme Java ci-dessous illustre l'utilisation d'un comparateur personnalisé pour l'ordre des éléments. Dans ce programme, nous définissons un nouveau comparateur personnalisé à l’intérieur duquel nous remplaçons la méthode «comparer». La méthode compare est utilisée pour ordonner les éléments de PriorityQueue en fonction de la longueur.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Production:
File d'attente de priorité minimale en Java
L'ordre naturel de la file d'attente prioritaire a le plus petit ou le plus petit élément en tête de la file d'attente et donc l'ordre est croissant. C'est ce qu'on appelle la «file d'attente de priorité minimale» avec l'ordre croissant des éléments.
Le programme Java ci-dessous montre l'implémentation de la file d'attente de priorité minimale en Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Production:
File d'attente de priorité maximale en Java
Alors que la file d'attente de priorité minimale a des éléments dans l'ordre croissant, la file d'attente de priorité maximale a les éléments dans l'ordre décroissant, c'est-à-dire que la tête de la file d'attente de priorité Max renverra le plus grand élément de la file d'attente.
comment déclarer une file d'attente en java
Le programme Java ci-dessous illustre la file d'attente de priorité maximale en Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Production:
Comme indiqué dans le programme ci-dessus, pour changer l'ordre naturel des éléments dans la file d'attente prioritaire, nous devons définir un comparateur personnalisé.
Questions fréquemment posées
Q # 1) Quelle est la file d'attente prioritaire en Java?
Répondre: Une file d'attente spéciale dans laquelle tous les éléments de la file d'attente sont classés selon l'ordre naturel ou à l'aide d'un comparateur personnalisé est appelée file d'attente prioritaire. Il ne suit pas l'ordre FIFO.
Q # 2) Comment définir une file d'attente de priorité maximale en Java?
Répondre: Nous pouvons définir une file d'attente de priorité maximale en Java à l'aide d'un comparateur personnalisé afin que la tête de la file d'attente renvoie le plus grand élément de la file d'attente.
Q # 3) La file d'attente Priority autorise-t-elle les doublons Java?
Répondre: Oui. La file d'attente prioritaire autorise les valeurs en double.
Q # 4) La file d'attente Java Priority est-elle max ou min?
Répondre: Par défaut, la file d'attente prioritaire en Java est la file d'attente prioritaire minimale avec un ordre naturel. Pour le rendre maximum, nous devons utiliser un comparateur personnalisé afin que la tête de la file d'attente renvoie le plus grand élément de la file d'attente.
Q # 5) Une file d'attente prioritaire est-elle triée?
Répondre: Par défaut, la tête de la file d'attente est triée et la file d'attente Prioritaire a le plus petit élément en tête. Le reste des éléments est commandé au besoin.
Conclusion
Ceci termine le didacticiel sur les files d'attente prioritaires en Java. Priority Queue implémente une interface de file d'attente et est une file d'attente spéciale où les éléments sont classés selon l'ordre naturel. Il ne suit pas l'ordre FIFO. Pour modifier l'ordre naturel de la file d'attente prioritaire, nous pouvons utiliser le comparateur personnalisé.
Les files d'attente prioritaires sont principalement utilisées pour la planification d'imprimante, la planification des tâches CPU, etc. Le tas (min ou max) est également implémenté à l'aide de files d'attente prioritaires.
=> Lisez la série de formations Easy Java.
lecture recommandée
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- File d'attente prioritaire dans STL
- File d'attente Java - Méthodes de file d'attente, implémentation de file d'attente avec des exemples
- Structure de données de file d'attente circulaire C ++: implémentation et applications
- File d'attente à double extrémité (Deque) en C ++ avec des exemples
- Structure de données de file d'attente en C ++ avec illustration
- Piles et files d'attente dans STL
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
