Java PriorityQueue

PriorityQueue<E> est le tas du JDK. C'est une Queue, mais au lieu du FIFO, la tête est toujours l'élément le plus petit selon un Comparator (ou l'ordre naturel si vous n'en fournissez pas). offer est en O(log n), poll et peek depuis la tête sont respectivement en O(log n) et O(1), et le stockage sous-jacent est un tableau plat — sans allocation de nœud par élément. C'est donc l'outil idéal pour les problèmes de type planificateur : « toujours traiter ce qui est le plus urgent en priorité. »

Ce que signifie « tête » ici

Pour une file FIFO, la tête est celui qui est arrivé en premier. Pour une PriorityQueue, la tête est celui qui a la plus petite valeur à cet instant — pas la plus petite au moment de l'insertion :

• peek() retourne le plus petit actuel.
• poll() supprime le plus petit actuel et rééquilibre ; le prochain peek affiche le nouveau plus petit.
• offer(x) insère et rééquilibre ; si x est le nouveau plus petit, le prochain peek le retourne.

« Plus petit » est déterminé par :

1. Le Comparator passé au constructeur, le cas échéant.
2. Sinon, l'ordre naturel de l'élément via Comparable. Si vos éléments ne sont pas Comparable et que vous n'avez pas passé de Comparator, le premier appel nécessitant une comparaison lance une ClassCastException.

Il n'existe pas de mode tas-maximum. Si vous voulez un tas-max, passez Comparator.reverseOrder() (ou votre comparateur personnalisé inversé) — c'est l'idiome standard, que nous utilisons dans l'exemple ci-dessous.

Créer une PriorityQueue

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

Le constructeur à un seul argument qui prend une Collection est en O(n) — il construit le tas en bloc plutôt que par n opérations offer en O(log n). Utile quand vous avez déjà toutes les données disponibles dès le départ.

L'itération n'est PAS dans l'ordre de priorité

C'est la surprise que la plupart des gens rencontrent une fois. Itérer sur une PriorityQueue parcourt le tableau du tas sous-jacent dans l'ordre dans lequel le tas stocke ses nœuds — pas dans l'ordre croissant :

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + " "); // possibly: 10 20 30 40
                                            // possibly: 10 40 30 20

L'ordre d'affichage est un détail d'implémentation de la disposition du tas. Si vous voulez les éléments dans l'ordre de priorité, vous devez les extraire :

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // sorted

Gardez cela à l'esprit lorsque vous utilisez forEach, stream, toArray, ou que vous affichez simplement la file pour déboguer. Le Stream retourné par stream() n'est pas trié, et lui ajouter .sorted() requiert que les éléments soient Comparable (ou vous pouvez passer un comparateur).

Muter un élément après offer casse le tas

La priorité est calculée au moment de l'insertion. Si vous insérez un élément puis modifiez le champ que le comparateur examine, le tas se trouve dans un état invalide — poll peut retourner la mauvaise tête, contains peut rater des éléments, vous perdez l'invariant. Il n'existe pas de méthode update ou decrease-key.

Les deux solutions de contournement :

• Utilisez des éléments immuables — des records avec des champs de priorité, ou des records enveloppeurs comme record Task(int priority, String name) {}. Ainsi, rien ne peut être muté après l'insertion.
• Supprimez et réinsérez si vous avez vraiment besoin de changer la priorité : pq.remove(task) est en O(n) (il effectue une recherche), puis pq.offer(taskWithNewPriority) est en O(log n).

Pour une petite file, supprimer-et-réinsérer convient très bien. Pour « je réécris l'algorithme de Dijkstra et j'ai besoin d'un decrease-key rapide », une PriorityQueue n'est pas le bon outil — il vous faut un tas indexé ou un TreeSet de paires (priority, node).

null et sécurité des threads

Mêmes règles que pour le reste de Queue :

• Pas de nulls. pq.offer(null) lance une NullPointerException.
• Non thread-safe. L'accès concurrent nécessite PriorityBlockingQueue, le cousin dans java.util.concurrent.

Un exemple concret : un mini planificateur de tâches

Le programme ci-dessous utilise une PriorityQueue pour planifier des tâches par priorité (numéro inférieur = plus urgent). Il illustre également l'idiome du tas-max et la surprise de l'ordre d'itération.

Lecture de l'exécution :

• toString() et forEach ont affiché les tâches dans un certain ordre — pas trié. N'utilisez ni l'un ni l'autre pour déboguer « la priorité est-elle correcte ? » — extrayez avec poll pour voir le vrai ordre.
• Le constructeur en bloc a produit un tas correctement ordonné en une seule opération — c'est le chemin de tasification en temps linéaire.
• Le bloc de mutation à la fin est le piège concentré à l'état pur. Nous avons muté la priorité du tableau après l'avoir inséré, le tas n'a pas eu la possibilité de se rééquilibrer, et maintenant peek ment. La solution est soit d'utiliser un enveloppeur immuable, soit de faire remove-et-offer après le changement.

Et ensuite

Le prochain chapitre couvre l'implémentation vers laquelle vous vous tournez quand vous voulez une file FIFO ou une pile ou une deque — et celle que le Javadoc du JDK vous recommande par défaut pour les trois : ArrayDeque. C'est la classe qui effectue la majeure partie du travail en coulisse dans le code d'exemple des deux chapitres précédents.

Pratique