File d’attente de priorité Java

Tutoriels
Java

De temps en temps, nous avons besoin de traiter des éléments d’une file d’attente dans un ordre particulier. La file d’attente prioritaire est une structure de données qui fait le travail. La file d’attente prioritaire en Java est différente de la « file d’attente » normale. Au lieu de suivre le principe du « premier entré, premier sorti », elle récupère les éléments selon leur priorité.

File d’attente prioritaire en Java

La classe java.util.PriorityQueue nous fournit une implémentation de ce type de données en utilisant une implémentation de tas prioritaire en interne. La file d’attente prioritaire en Java est une file d’attente non bornée. Elle a été introduite dans Java 1.5 et améliorée dans la version Java SE 8. La file d’attente prioritaire est implémentée en interne en utilisant une structure de données appelée « tas prioritaire ». Voici la hiérarchie de classes de PriorityQueue : Diagramme de classe de PriorityQueue :

Constructeurs de PriorityQueue en Java

  1. PriorityQueue() – Crée une file d’attente prioritaire avec une capacité initiale par défaut, c’est-à-dire 11
  2. PriorityQueue(Collection c) – Crée une file d’attente prioritaire avec les éléments de la collection spécifiée.
  3. PriorityQueue(int initialCapacity) – Crée une file d’attente prioritaire avec la capacité initiale spécifiée
  4. PriorityQueue(int initialCapacity, Comparator comparator) – Crée une file d’attente prioritaire avec la capacité initiale fournie et l’ordonnancement de ses éléments est selon le comparateur spécifié
  5. PriorityQueue(PriorityQueue c) – Crée une file d’attente prioritaire contenant les éléments de la file d’attente prioritaire spécifiée
  6. PriorityQueue(SortedSet c) – Crée une file d’attente prioritaire contenant les éléments de l’ensemble trié spécifié

Les éléments de la file d’attente prioritaire sont ordonnés selon leur ordre naturel à moins que nous ne fournissions un Comparator lors de sa création. Les éléments sont ordonnés par défaut dans l’ordre croissant, donc la tête de la file est l’élément dont la priorité est la plus basse. S’il y a deux éléments éligibles pour devenir la tête en même temps, ce genre de liens est rompu arbitrairement.

Exemple de PriorityQueue en Java

Créons une PriorityQueue, contenant diverses tâches:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

Cela crée une PriorityQueue de tâches, qui seront ordonnées selon l’ordre naturel de String. Créons ensuite une autre PriorityQueue qui ordonne les tâches dans l’ordre inverse de l’ordre naturel. Nous devons donc passer un Comparateur:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Méthodes de PriorityQueue Java

Jetons un coup d’œil à toutes les méthodes disponibles pour PriorityQueue et utilisons-les :

  1. Boolean add(E e) – Cette méthode insère l’élément spécifié dans la file d’attente. Nous avons déjà ajouté 5 tâches dans notre file d’attente en utilisant cette méthode.

  2. Comparator comparator() – Cette méthode renvoie le comparateur utilisé pour ordonner les éléments dans cette file d’attente. Elle renvoie null si aucun comparateur n’a été spécifié et si la file d’attente est triée selon l’ordre naturel de ses éléments. Donc, si nous faisons :

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    Le résultat sera :

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – Renvoie vrai si la file d’attente contient l’élément spécifié. Vérifions si « task3 » appartient à la file d’attente de priorité des tâches :

    System.out.println(tasks.contains("task3"));

    Cela imprime :

    true

  4. boolean offer(E e) – Tout comme la méthode add(), cette méthode ajoute également un élément à la file d’attente. Les méthodes offer() et add() sont en fait un peu différentes pour les files d’attente contraintes par capacité, mais dans le cas de PriorityQueue, les deux sont identiques. Contrairement à add(), offer() ne lance pas d’exception même si elle échoue à ajouter l’élément dans la file d’attente.

  5. E peek() – Récupère la tête de cette file d’attente, ou renvoie null si cette file d’attente est vide. En d’autres termes, cela renvoie l’élément ayant la priorité la plus élevée. Ainsi, le code suivant :

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    Nous donne :

    task1
task5

  6. E poll() – Cette méthode récupère également la tête de la file d’attente (l’élément avec la plus haute priorité), ou renvoie null si la file d’attente est vide. Mais contrairement à peek(), elle supprime également l’élément. Ainsi, si nous appelons poll():

    System.out.println(“Poll sur les tâches: ”+tasks.poll());
System.out.println(“Poll sur reverseTasks: ”+reverseTasks.poll());

    Et ensuite peek:

    System.out.println(“Peek sur les tâches: ”+tasks.peek());
System.out.println(“Peek sur reverseTasks: ”+reverseTasks.peek());

    Nous aurons la sortie suivante:

    Poll sur les tâches: tâche1
Poll sur reverseTasks: tâche5
Peek sur les tâches: tâche2
Peek sur reverseTasks: tâche4

  7. int size() – Renvoie le nombre d’éléments dans la file d’attente.

  8. boolean remove(Object o) – Supprime l’élément spécifié de la file d’attente, s’il est présent. Si deux éléments identiques sont présents, il en supprime seulement un.

  9. Object[] toArray() – Renvoie un tableau contenant tous les éléments de la file d’attente.

  10. T[] toArray(T[] a) – Renvoie un tableau contenant tous les éléments dans la file d’attente, et le type du tableau renvoyé est celui du tableau spécifié.

  11. Iterator iterator() – Renvoie un itérateur pour la file d’attente.

  12. void clear() – Supprime tous les éléments de la file d’attente.

En plus de cela, la classe PriorityQueue hérite également des méthodes des classes Collection et Object.

Complexité temporelle de Java PriorityQueue

  1. Pour les méthodes d’enfilement et de défilement, la complexité temporelle est O(log(n))
  2. Pour les méthodes remove(Object) et contains(Object), la complexité temporelle est linéaire
  3. Pour les méthodes de récupération, elle a une complexité temporelle constante

Cette implémentation de la file d’attente prioritaire n’est pas thread-safe. Donc, si nous avons besoin d’un accès synchronisé, nous devons utiliser PriorityBlockingQueue. Référence: Documentation de l’API

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java