À retenir
- L'élément extrait est toujours celui ayant la plus haute priorité.
- Contrairement à une file classique (FIFO), l'ordre d'entrée ne garantit pas l'ordre de sortie.
- Elle est indispensable pour les algorithmes d'optimisation et de planification.
Une file de priorité est une liste d'attente intelligente où les éléments ne sortent pas forcément dans leur ordre d'arrivée, mais selon leur importance. C'est comme un service d'urgences à l'hôpital : même si vous êtes arrivé le premier pour une petite égratignure, une personne arrivant plus tard avec une blessure grave passera devant vous car sa priorité est plus élevée.
Étymologie
Traduction du concept anglais priority queue. Le terme combine la structure de données classique de la « file » (queue) avec la notion mathématique de « priorité » (poids ou valeur affectée à un élément) pour dicter l'ordre de traitement.
Exemples d'usage
- Le gestionnaire de tâches d'un ordinateur qui donne la priorité aux processus système vitaux par rapport à une impression en cours.
- L'algorithme de Dijkstra qui utilise une file de priorité pour trouver le chemin le plus court sur une carte GPS.
- Le codage de Huffman utilisé pour la compression de fichiers (ZIP, JPEG).
Cas d'usage
Ce concept intervient massivement dans les systèmes d'exploitation pour la gestion du processeur, dans les réseaux pour prioriser les flux vidéo (streaming) sur les e-mails, et dans l'intelligence artificielle pour explorer les solutions les plus prometteuses d'un problème en premier.
Bonnes pratiques
Pour garantir de bonnes performances, il est déconseillé d'utiliser un simple tableau trié. On privilégie généralement une structure appelée tas (heap), qui permet d'insérer et d'extraire des éléments très rapidement, même quand la file contient des millions de données.
Synonymes
Antonymes
Conseil
Si vous débutez en programmation, ne réinventez pas la roue : la plupart des langages (Java, Python, C++, C#) proposent déjà des bibliothèques prêtes à l'emploi pour gérer les files de priorité de manière optimisée.
Questions fréquentes
Quelle est la différence avec une file classique ?
Dans une file classique (FIFO), le premier arrivé est le premier servi. Dans une file de priorité, c'est le plus urgent qui est servi en premier.
Que se passe-t-il si deux éléments ont la même priorité ?
Généralement, on applique alors la règle du premier arrivé, premier servi pour ces deux éléments précis.