Une PriorityQueue (ou file prioritaire) est une structure de données essentielle lorsqu’on souhaite traiter des éléments selon un ordre défini par leur priorité plutôt que par leur ordre d’arrivée. Contrairement à une Queue classique, qui fonctionne sur le principe du FIFO (First-In, First-Out), une PriorityQueue sélectionne toujours l’élément avec la priorité la plus basse pour traitement. Cela permet d’implémenter facilement des mécanismes de tri dynamique dans des contextes comme les algorithmes de recherche, les planificateurs de tâches ou les systèmes de messagerie.

La PriorityQueue en C#

Introduite en C# 10 avec .NET 6, la classe PriorityQueue fournie par le namespace System.Collections.Generic simplifie considérablement la gestion des files prioritaires. Chaque élément stocké est associé à une valeur de priorité, qui peut être un entier, une chaîne ou même un objet complexe, selon le besoin.

Ces caractéristiques la rendent idéale pour des algorithmes comme Dijkstra, A* ou même pour des systèmes d’ordonnancement plus simples.

Par défaut, les éléments sont traités dans l’ordre croissant de priorité. Autrement dit, une priorité de 1 sera traitée avant une priorité de 10. Cela peut paraître contre-intuitif au début, mais c’est cohérent avec la logique de « plus petite valeur = plus haute priorité ».

Prenons l’exemple suivant avec une classe Employee :

public class Employee
{
    public int Id { get; set; }
    public string Name { get; set; }

    public Employee(int id, string name)
    {
        Id = id;
        Name = name;
    }

    public override string ToString() => $"Id: {Id}, Name: {Name}";
}

Nous pouvons créer une file prioritaire triant les employés selon une priorité numérique :

var queue = new PriorityQueue<Employee, int>();

queue.Enqueue(new Employee(1, "Alice"), 30);
queue.Enqueue(new Employee(2, "Bob"), 15);
queue.Enqueue(new Employee(3, "Charlie"), 20);

On utilise Peek() pour consulter l’élément suivant sans le retirer :

Employee first = queue.Peek();
Console.WriteLine(first); // Bob (plus basse priorité = 15)

Et Dequeue() pour le retirer de la collection :

Employee removed = queue.Dequeue();
Console.WriteLine(removed); // Bob 15

removed = queue.Dequeue();
Console.WriteLine(removed);  // Charlie 20

Personnalisation avec un comparer

Par défaut, la PriorityQueue utilise l’ordre naturel du type TPriority. Mais il est possible de personnaliser cet ordre avec un IComparer.

Par exemple, si l’on veut traiter les employés ayant les IDs les plus élevés en priorité, on peut créer un comparateur :

public class EmployeeComparer : IComparer<Employee>
{
    public int Compare(Employee x, Employee y)
    {
        return y.Id.CompareTo(x.Id); // ordre décroissant
    }
}

Et créer une PriorityQueue<Employee, Employee> qui utilisera ce Comparer :

var employees = new List<Employee>
{
    new Employee(1, "Alice"),
    new Employee(2, "Bob"),
    new Employee(3, "Charlie")
};

var queue = new PriorityQueue<Employee, Employee>(new EmployeeComparer());

foreach (var emp in employees)
{
    queue.Enqueue(emp, emp);
}

while (queue.Count > 0)
{
    Console.WriteLine(queue.Dequeue());
}
// Charlie (3), Bob (2), Alice (1) par ordre d'Id décroissant

Conclusion

La PriorityQueue est une structure simple en apparence, mais puissante dans ses usages. Grâce à sa flexibilité et à sa facilité d’utilisation, elle permet de répondre à des besoins variés en matière de gestion d’ordre, d’optimisation, ou encore de traitement asynchrone. Elle devient rapidement un outil incontournable dès lors qu’une notion de priorité est nécessaire dans une application.