Commençons par explorer les besoins d'une file de priorité et la structure des tas binaires. Cet article couvre la théorie, la mise en œuvre en code sera abordée ultérieurement.

Un scénario pratique

Considérons une situation où un thread secondaire doit continuellement extraire des tâches d'une file pour les exécuter, en s'assurant que les tâches à haute priorité sont traitées en premier. Par exemple, si 10 tâches sont déjà dans la file et qu'une tâche urgente survient, comment garantir son exécution prioritaire ?

Solutions alternatives et leurs limites

Plusieurs approches existent :

1. Utiliser un tableau : les tâches sont stockées et triées par priorité à chaque insertion, permettant une extraction rapide par la tête. Cependant, l'insertion nécessite de parcourir tout le tableau pour trouver la position adéquate, avec une complexité temporelle de O(n) à l'insertion et O(1) à l'extraction.
2. Utiliser une liste chaînée : similaire au tableau, l'insertion nécessite de parcourir la liste pour placer l'élément selon sa priorité, avec une complexité de O(n) à l'insertion et O(1) à l'extraction.

Ces méthodes souffrent d'une faible efficacité à l'insertion. La PriorityQueue en Java offre une solution optimale avec une complexité logarithmique pour l'insertion et l'extraction.

Exemple d'utilisation de la PriorityQueue

Créons une classe représentant une tâche avec une priorité :

public class Job {
    private String description;
    private int urgency;

    public Job(String description, int urgency) {
        this.description = description;
        this.urgency = urgency;
    }

    public void execute() {
        System.out.println("Exécution de la tâche...");
    }

    @Override
    public String toString() {
        return "Job: " + description + ", Urgence: " + urgency;
    }
}

Testons la PriorityQueue avec un comparateur :

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestPriority {
    public static void main(String[] args) {
        Comparator<Job> priorityComparator = (job1, job2) -> Integer.compare(job2.getUrgency(), job1.getUrgency());

        Queue<Job> jobQueue = new PriorityQueue<>(10, priorityComparator);

        jobQueue.add(new Job("Rapport financier", 50));
        jobQueue.add(new Job("Réunion client", 85));
        jobQueue.add(new Job("Mise à jour logiciel", 30));
        jobQueue.add(new Job("Correction de bug critique", 100));

        System.out.println(jobQueue.poll()); // Correction de bug critique
        System.out.println(jobQueue.poll()); // Réunion client
        System.out.println(jobQueue.poll()); // Rapport financier
        System.out.println(jobQueue.poll()); // Mise à jour logiciel
    }
}

La sortie montre que les tâches sont extraites par ordre de priorité décroissante, indépendamment de leur ordre d'insertion.

Fonctionnement interne de la PriorityQueue

La PriorityQueue en Java repose sur les principes suivants :

• Elle utilise un tas max (ou min) pour organiser les éléments.
• Un tas est un arbre binaire complet où chaque nœud parent est supérieur (ou inférieur) à ses enfants.
• Les éléments sont stockés dans un tableau pour une représentation efficace.

1. Qu'est-ce qu'un arbre binaire complet ?

Un arbre binaire complet a tous ses niveaux remplis de gauche à droite, sauf possiblement le dernier qui est également rempli de gauche à droite. Cette structure garantit une hauteur logarithmique et permet une implémentation par tableau.

2. Structure d'un tas max

Un tas max satisfait deux conditions :

1. C'est un arbre binaire complet.
2. La valeur de chaque nœud parent est supérieure ou égale à celles de ses enfants.

Ainsi, la racine contient toujours l'élément de priorité maximale.

Représentation par tableau

Pour un arbre binaire complet, les éléments sont stockés dans un tableau à partir de l'index 1 pour faciliter les calculs :

• Pour un nœud à l'index i :
  • Enfant gauche : 2 * i
  • Enfant droit : 2 * i + 1
  • Parent : i / 2 (division entière)

Ces relations permettent de naviguer dans l'arbre sans pointeurs explicites.

Insertion dans le tas

Pour insérer un nouvel élément :

1. Ajouter l'élément à la fin du tableau (à l'index size + 1, en étendant le tableau si nécesssaire).
2. Rétablir la propriété du tas par un processus de "percolation vers le haut" : comparer l'élément avec son parent et les échanger si nécessaire, en répétant jusqu'à ce que la condition soit satisfaite.

Cette opération a une complexité de O(log n) dans le pire cas.

Suppression de la racine

Pour extraire l'élément maximum (racine) :

1. Remplacer la racine par le dernier élément du tableau.
2. Rétablir la propriété du tas par un processus de "percolation vers le bas" : comparer l'élément avec ses enfants et l'échanger avec le plus grand enfant si nécessaire, en répétant jusqu'à ce que la condition soit satisfaite.

Cette opération a également une complexité de O(log n).

Ces mécanismes assurent une efficacité optimale pour les opérations de base, faisant de la PriorityQueue une structure idéale pour les besoins de files d'attente prioritaires.