Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
File de priorité
Résumé
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 ;
extraire 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.
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.
Une implémentation simple de la file de priorité consiste à utiliser une liste chaîné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 :
En Python, le module heapq implémente la file de priorité.
En C++, la STL fournit une implémentation nommée priority_queue. 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.
En Java, c'est la classe PriorityQueue qui implémente la file de priorité.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (3)
Concepts associés (35)
Collection (type de données)
En programmation informatique, une collection est un regroupement d'un nombre variable d'éléments de données (éventuellement zéro) qui ont une signification commune pour le problème à résoudre et qui doivent être traités ensemble d'une manière contrôlée. En général, les éléments de données sont du même type ou, dans les langages supportant l'héritage, dérivés d'un type ancêtre commun.
Tas (informatique)
vignette|Un exemple de tas. Il contient 9 éléments. L'élément le plus prioritaire (100) est à la racine. En informatique, un tas (ou monceau au Canada, heap en anglais) est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. C'est un arbre binaire presque complet ordonné. Un arbre binaire est dit presque complet si tous ses niveaux sont remplis, sauf éventuellement le dernier, qui doit être rempli sur la gauche (cf. Contre-exemples).
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 ; extraire 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.
Cours associés (7)
CS-250: Algorithms
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
ME-213: Programmation pour ingénieur
Mettre en pratique les bases de la programmation vues au semestre précédent. Développer un logiciel structuré. Méthode de debug d'un logiciel. Introduction à la programmation scientifique. Introductio
CS-307: Introduction to multiprocessor architecture
Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce
Séances de cours associées (100)
Programmation Python : Tri et indexation
Couvre les concepts de programmation Python liés au tri et à l'indexation.
Sauts et files d'attente prioritaires
Explore les tas, les tris de tas et les files d'attente prioritaires, y compris les opérations et l'analyse.
Integers: Concepts élémentaires
Couvre les concepts fondamentaux liés aux entiers, y compris les propriétés des ensembles bien ordonnés et le principe d'induction.