File de priorité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

  • insérer un élément
  • lire puis supprimer l'élément ayant la plus grande clé
  • tester si la file de priorité est vide ou pas

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

Implémentations[modifier | modifier le code]

Une implémentation simple de la file de priorité consiste à utiliser une liste chaînée. Dans ce cas, la complexité de l'insertion est O(1) mais celle de la suppression du plus grand élément est linéaire en la taille de la structure. Cette solution est inefficace sauf dans certains cas particuliers : par exemple, l'algorithme de Dijkstra et l'algorithme de Prim appliqués à un graphe complet.

La STL fournit une implémentation nommée priority_queue[1]. Ce type de file se base au choix sur un des conteneurs présents dans la STL (liste, vecteur,...) 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.

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). Les principales sont le tas, le tas binomial et le tas de Fibonacci.

Utilisation notable[modifier | modifier le code]

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[modifier | modifier le code]

  1. priority_queue sur la documentation de STL