0Pricing
Java Academy · Leçon

PriorityQueue pour le traitement ordonné

Utilisez PriorityQueue avec l’ordre naturel et des comparateurs personnalisés dans des situations de planification de tâches.

PriorityQueue pour le traitement ordonné est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.

Qu’est-ce qu’une PriorityQueue ?

Une PriorityQueue est par défaut un tas min : l’élément dont l’ordre naturel est le plus petit se trouve toujours en tête. Les éléments ne sont pas triés en interne : seul le minimum est garanti en tête.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Structure interne du tas

PriorityQueue utilise un tas min binaire stocké dans un tableau. Le parent à l’indice i est toujours inférieur ou égal à ses enfants aux indices 2i+1 et 2i+2. Cela garantit des opérations offer/poll en O(log n) et peek en O(1).

Tas max avec un comparateur inversé

Pour créer un tas max, avec le plus grand élément en premier, transmettez Comparator.reverseOrder() :

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

PriorityQueue avec des objets personnalisés

Utilisez un comparateur pour ordonner des enregistrements ou des classes personnalisés :

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek contre Poll

peek() renvoie l’élément en tête sans le supprimer. poll() le supprime et le renvoie. Les deux renvoient null lorsque la file est vide, contrairement à element()/remove(), qui lèvent une exception.

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

Exemple d’ordonnancement de tâches

PriorityQueue est idéale pour les simulations d’ordonnancement du CPU dans lesquelles les tâches ont des priorités différentes :

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

Les K plus petits éléments

PriorityQueue est un outil classique pour trouver les K plus petits éléments sans trier entièrement le tableau :

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

Les K plus grands éléments avec un tas max

Autre possibilité : maintenez un tas min de taille K pendant le parcours afin de trouver les K plus grands éléments :

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Principe de l’algorithme de Dijkstra

L’algorithme des plus courts chemins de Dijkstra s’appuie sur un tas min pour toujours développer en premier le nœud non visité le moins coûteux :

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

Le parcours n’est pas ordonné

Parcourir une PriorityQueue avec une boucle de parcours ne renvoie PAS les éléments dans l’ordre des priorités : seule l’opération poll() le garantit. Pour obtenir une sortie triée, appelez poll à plusieurs reprises au lieu d’utiliser une boucle de parcours.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

Résumé des performances

Complexité des opérations de PriorityQueue :

  • offer(e) : O(log n)
  • poll() : O(log n)
  • peek() : O(1)
  • contient(e) : O(n)
  • supprime(e) : O(n)

Elle n’est pas sûre pour les accès concurrents : utilisez PriorityBlockingQueue pour les accès simultanés.

Vérification rapide

Que garantit l’ordre des éléments lorsqu’une PriorityQueue est parcourue avec une boucle de parcours ?

Récapitulatif : PriorityQueue

Points essentiels :

  • PriorityQueue est un tas min : le plus petit élément est extrait en premier
  • Utilisez Comparator.reverseOrder() pour créer un tas max
  • offer/poll en O(log n), peek en O(1)
  • Cas d’utilisation classiques : K-ième plus grand ou plus petit élément, Dijkstra et ordonnancement de tâches
  • Une boucle de parcours ne fournit pas l’ordre des priorités : utilisez poll()

Questions Fréquemment Posées

La leçon « PriorityQueue pour le traitement ordonné » est-elle gratuite ?

Oui — le texte complet de « PriorityQueue pour le traitement ordonné » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « PriorityQueue pour le traitement ordonné » ?

Utilisez PriorityQueue avec l’ordre naturel et des comparateurs personnalisés dans des situations de planification de tâches. Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Java Academy ?

Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « PriorityQueue pour le traitement ordonné » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?

Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Fonctionnement interne de LinkedList
  2. Opérations sur une deque : pile et file
  3. LinkedList et ArrayList : compromis
  4. PriorityQueue pour le traitement ordonné
← Retour à Java Academy