Files de priorité et tas

Une file de priorité est un type de données abstrait qui fournit toujours l'élément de priorité la plus élevée (ou la plus basse) ; les tas sont les structures arborescentes standard qui l'implémentent avec des opérations d'insertion et d'extraction du minimum efficaces.

Definition

Une file de priorité est un type de données abstrait permettant l'insertion d'éléments avec des priorités et l'extraction de l'élément de priorité la plus élevée ; un tas est une structure de données arborescente satisfaisant la propriété de tas — la clé de chaque nœud est ordonnée de manière cohérente par rapport à ses enfants — qui implémente une file de priorité de manière efficace.

Scope

Ce sujet aborde le type de données abstrait (TDA) de file de priorité et ses implémentations basées sur des tas : le tas binaire et sa représentation en tableau, la propriété de tas et les opérations de tamisage vers le haut (sift-up) / tamisage vers le bas (sift-down), le tri par tas (heapsort), ainsi que les tas fusionnables avancés tels que les tas binomiaux et de Fibonacci qui améliorent les coûts de diminution de clé et d'union. Il est lié aux algorithmes de graphes (Dijkstra, Prim) et à la simulation à événements discrets, qui reposent sur les files de priorité.

Core questions

• Quelles opérations définissent le TDA de file de priorité, et comment un tas les implémente-t-il ?
• Comment la propriété de tas permet-elle de trouver le minimum en temps constant et d'insérer/extraire en temps logarithmique ?
• Comment un tas binaire est-il stocké de manière compacte dans un tableau, et comment en construit-on un en temps linéaire ?
• Comment le tri par tas (heapsort) utilise-t-il un tas pour trier en place en temps O(n log n) ?
• Quand les tas fusionnables, tels que les tas de Fibonacci, améliorent-ils les algorithmes qui diminuent fréquemment les clés ?

Key concepts

• TDA de file de priorité
• propriété de tas
• tas binaire
• représentation de tas basée sur un tableau
• tamisage vers le haut (sift-up) et tamisage vers le bas (sift-down)
• construction de tas (build-heap) en temps linéaire
• tri par tas (heapsort)
• tas de Fibonacci et binomiaux

Key theories

Propriété de tas et représentation en tableau

Un tas binaire est un arbre binaire presque complet dans lequel la clé de chaque nœud domine celles de ses enfants ; il peut être stocké dans un tableau avec un indexage parent-enfant implicite, permettant des opérations d'insertion et d'extraction en O(log n) et de recherche du minimum en O(1).

Efficacité amortie des tas de Fibonacci

Les tas de Fibonacci permettent la diminution de clé (decrease-key) en temps amorti O(1) et l'extraction du minimum (extract-min) en temps amorti O(log n), améliorant ainsi le temps d'exécution asymptotique d'algorithmes tels que ceux de Dijkstra et de Prim qui effectuent de nombreuses diminutions de clé.

Clinical relevance

Les files de priorité constituent une infrastructure essentielle : elles ordonnent les tâches prêtes dans les ordonnanceurs de systèmes d'exploitation, gèrent les événements dans la simulation à événements discrets, pilotent la recherche en premier le meilleur (best-first) et A*, et définissent la frontière dans les algorithmes de Dijkstra et de Prim. Le tri par tas (heapsort) offre un tri en place en O(n log n) avec des bornes garanties dans le pire des cas.

History

J. W. J. Williams a introduit le tas binaire et le tri par tas (heapsort) en 1964, et Robert Floyd a proposé la procédure de construction de tas (build-heap) en temps linéaire peu après. Les tas binomiaux (Vuillemin, 1978) et les tas de Fibonacci (Fredman et Tarjan, 1987) ont ajouté des fusions efficaces et une diminution de clé amortie, affinant les temps d'exécution des algorithmes de graphes classiques.

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

Pourquoi stocker un tas binaire dans un tableau plutôt qu'avec des pointeurs ?

Un tas binaire est un arbre binaire presque complet, de sorte que ses nœuds se mappent proprement sur des indices de tableau consécutifs : un nœud à l'indice i a des enfants aux indices 2i et 2i+1. Cela évite la surcharge des pointeurs, améliore le comportement du cache et rend la navigation arithmétique simple.

Quand les tas de Fibonacci justifient-ils leur complexité ?

Les tas de Fibonacci offrent une diminution de clé (decrease-key) amortie en O(1), ce qui améliore le temps d'exécution asymptotique d'algorithmes comme les chemins les plus courts de Dijkstra sur des graphes denses. En pratique, leurs grands facteurs constants signifient que des tas binaires plus simples sont souvent plus rapides, de sorte qu'ils sont principalement pertinents pour les bornes théoriques et les cas spécialisés.