File de priorité
- File de priorité
-
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
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.
Références
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article File de priorité de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
File à priorité — File à priorités En informatique, une file à priorités est un type abstrait élémentaire sur laquelle on peut effectuer trois opérations: insérer un élément supprimer le plus grand élément tester si la file à priorités est vide ou pas Les… … Wikipédia en Français
File d'attente — à Berlin pour un concert en 1988. Une file d attente est un regroupement d individus attendant de manière organisée quelque chose. Les files d attente résultent d une demande supérieure à la capacité d écoulement d une offre (un bien ou un… … Wikipédia en Français
priorité — [ prijɔrite ] n. f. • 1361; lat. scolast. prioritas 1 ♦ Qualité de ce qui vient, passe en premier, dans le temps. Donner la priorité absolue à qqch. Nous discuterons ce point en priorité, en premier lieu. Zone à urbaniser en priorité (Z. U. P.).… … Encyclopédie Universelle
Priorite des ordres de bourse — Priorité des ordres de bourse La première sélection dans la priorité des ordres se fait d abord, par le prix. Un ordre d achat avec un cours supérieur aux autres, est placé en tête de la file des ordres en attente d exécution dans le carnet d… … Wikipédia en Français
Priorité des ordres de bourse — La première sélection dans la priorité des ordres se fait d abord, par le prix. Un ordre d achat avec un cours supérieur aux autres, est placé en tête de la file des ordres en attente d exécution dans le carnet d ordres. Un ordre de vente avec un … Wikipédia en Français
coupe-file — [ kupfil ] n. m. • 1869; de couper et file ♦ Carte officielle de passage, de priorité. Coupe file d un journaliste. Des coupe files. ● coupe file, coupe files nom masculin Laissez passer délivré par les services de police, qui permet de franchir… … Encyclopédie Universelle
Regles de priorite en France — Règles de priorité en France Il existe sur le réseau routier français cinq régimes de priorité : La priorité à droite Le stop Le Cédez le passage La priorité ponctuelle Le caractère prioritaire d une voie Sommaire 1 Les véhicules à moteur… … Wikipédia en Français
Règles de priorité en France — Il existe sur le réseau routier français cinq régimes de priorité : La priorité à droite Le stop Le Cédez le passage La priorité ponctuelle Le caractère prioritaire d une voie Sommaire 1 Les véhicules à moteur 1.1 La priorité à droite 1.2 … Wikipédia en Français
Règles de priorité en france — Il existe sur le réseau routier français cinq régimes de priorité : La priorité à droite Le stop Le Cédez le passage La priorité ponctuelle Le caractère prioritaire d une voie Sommaire 1 Les véhicules à moteur 1.1 La priorité à droite 1 … Wikipédia en Français
Scale-invariant feature transform — Exemple de résultat de la comparaison de deux images par la méthode SIFT (Fantasia ou Jeu de la poudre, devant la porte d’entrée de la ville de Méquinez, par Eug … Wikipédia en Français
