File de priorité

En informatique, une file de priorité est un type abstrait élémentaire sur laquelle on peut effectuer trois opérations[1] :

• enfiler un élément ;
• défiler l'élément ayant la plus grande clé ;
• tester si la file de priorité est vide ou pas.

Ainsi, elle permet d'implémenter efficacement des planificateurs de tâches, où un accès rapide aux tâches d'importance maximale est souhaité. On la retrouve par exemple dans les ordonnanceurs des systèmes d'exploitation, notamment le noyau Linux[2].

On ajoute parfois à cette liste l'opération « augmenter/diminuer la clé d'un élément », utilisée par exemple dans l'algorithme de Dijkstra.

Implémentations

Une implémentation simple de la file de priorité consiste à utiliser une liste chaînée non triée. Dans ce cas, la complexité de l'insertion serait O(1) mais celle de l'extraction du plus grand élément serait linéaire en la taille de la structure, causée par la recherche de l'élément de clé maximale. Cette solution est donc inefficace.

D'autres implémentations permettent de réaliser toutes les opérations efficacement, c'est-à-dire en O(1) ou O(log n) (éventuellement en complexité amortie). La principale est le tas, lui-même implémenté via un tableau. D'autres améliorations, plus difficiles à implémenter, existent, telles que le tas binomial et le tas de Fibonacci.

La file de priorité est déjà implémentée dans plusieurs langages de programmation :

1. En Python, le module heapq[3] implémente la file de priorité.
2. En C++, la STL fournit une implémentation nommée priority_queue[4]. Ce type de file se base sur un des conteneurs présents dans la STL (liste, vecteur, etc.) et manipule des objets d'un type défini par l'utilisateur. Il est nécessaire de fournir une fonction de comparaison qui permettra à la bibliothèque d'ordonner la file.
3. En Java, c'est la classe PriorityQueue[5] qui implémente la file de priorité.

Tri par file de priorité

Un tri par file de priorité est un algorithme de tri utilisant comme unique support une implémentation de file de priorité et donc seulement ses trois opérations classiques : enfiler, défiler et tester le vide[6].

Beaucoup d'algorithmes de tri classiques sont des tris par file de priorité. On y retrouve naturellement tous les tris par tas comme le tri par tas binaire ou le smoothsort. Mais aussi des tris plus classiques comme le tri par insertion et le tri par sélection. Enfin, de façon moins connue, avec des files de priorités implémentées par des arbre binaire de recherche on retrouve le tri arborescent et son cas particulier le tri rapide.

Utilisations notables

Les algorithmes suivants doivent leur efficacité à la structure de tas :

• Tri par tas
• Algorithme de Dijkstra pour la recherche de plus court chemin dans un graphe ;
• Algorithme de Prim pour la recherche d'arbre couvrant de poids minimal dans un graphe.

La file de priorité peut notamment être utilisée comme optimisation de l'algorithme algorithme A* en facilitant l'accès au meilleur nœud stocké dans la liste des nœuds ouverts (open list).

Références

1. François Schwarzentruber, « File de priorité et tas binaire » [PDF], 18 février 2021 (consulté le 16 octobre 2024)
2. Exemples d'algorithmes et de structures de données couramment utilisées, notamment dans le noyau Linux, sur Stack Overflow (en)
3. Documentation Python 3.10 sur une implémentation des files de priorité
4. priority_queue sur la documentation de STL
5. Documentation Java 8 SE sur l'implémentation des files de priorité (en)
6. « File de priorité » [PDF] (consulté le 17 octobre 2024)