Worldlex Wiki 
structure de données qui implémente le type abstrait de file de priorité : elle gère une collection dynamique d'éléments dotés de priorités numériques et permet un accès rapide à l'élément de priorité minimale (ou maximale). Dans une file à compartiments, les priorités doivent être des entiers , et cette structure est particulièrement adaptée aux applications où les priorités ont un intervalle restreint. Une file à compartiments se présente sous la forme d'un tableau de compartiments : une structure de données de type tableau , indexée par les priorités, dont les cellules contiennent des collections d'éléments de même priorité. Avec cette structure de données, l'insertion d'éléments et la modification de leur priorité s'effectuent en temps constant . La recherche et la suppression de l'élément de priorité minimale prennent un temps proportionnel au nombre de compartiments ou, en conservant un pointeur vers le compartiment le plus récemment trouvé, un temps proportionnel à la différence de priorités entre deux opérations successives.
La file à compartiments est l'équivalent, pour les files de priorité, du tri par tiroirs (ou tri par casiers), un algorithme de tri qui place les éléments dans des compartiments indexés par leur priorité, puis concatène ces compartiments. L'utilisation d'une file à compartiments comme file de priorité dans un tri par sélection reproduit l'algorithme du tri par tiroirs. Les files à compartiments sont également appelées files de priorité à compartiments ou files de priorité à hauteur bornée . Lorsqu'elles sont utilisées pour des approximations quantifiées des priorités de nombres réels , elles sont aussi appelées files de priorité désordonnées ou files de priorité pseudo-ordonnées . Elles sont étroitement liées à la file calendaire , une structure qui utilise un tableau similaire de compartiments pour une priorisation exacte par nombres réels.
Les applications de la file d'attente à seaux incluent le calcul de la dégénérescence d'un graphe , des algorithmes rapides pour les plus courts chemins et les plus longs chemins dans les graphes dont les poids sont de petits entiers ou déjà triés, ainsi que des algorithmes d'approximation gloutons pour le problème de la couverture d'ensembles . La version quantifiée de cette structure a également été appliquée à l'ordonnancement et à l' algorithme des cubes en marche en infographie . La première utilisation de la file d'attente à seaux structures de données conteneurs ; dans la plupart des sources, ces conteneurs sont des listes doublement chaînées, mais il peut également s'agir de tableaux dynamiques ou d'ensembles dynamiques . Le conteneur de la recherche séquentielle dans le tableau pour trouver respectivement le premier ou le dernier conteneur non vide, choisissez un élément arbitraire dans ce conteneur et retirez-le du conteneur. De cette manière, les insertions et les changements de priorité prennent un temps constant, et l'extraction de l'élément de priorité minimale ou maximale prend un temps inférieure de la priorité minimale de tout élément présent dans la file d'attente. Lors de l'insertion d'un nouvel élément, l'algorithme de Dijkstra , les priorités minimales forment une suite monotone , permettant ainsi l'utilisation d'une file de priorité monotone . Dans ces applications, pour les variantes paresseuse et active de la structure optimisée, les recherches séquentielles de compartiments non vides couvrent des intervalles disjoints de compartiments. Puisque chaque compartiment appartient à au plus un de ces intervalles, la somme des nombres d'étapes est au plus égale à Donald B. Johnson en 1981 stocke uniquement les compartiments non vides dans une liste chaînée, triée par priorité, et utilise un arbre de recherche auxiliaire pour trouver rapidement la position de tout nouveau compartiment dans cette liste. L'initialisation de cette structure variante prend un temps
Applications
dégénérescence des graphes
Une file d'attente à compartiments permet de gérer les sommets d'un graphe non orienté , classés par ordre de priorité selon leur degré , et de rechercher et supprimer itérativement le sommet de degré minimal. Cet algorithme glouton permet de calculer la dégénérescence d'un graphe donné, égale au degré maximal de ses sommets au moment de leur suppression. L'algorithme s'exécute en temps linéaire , avec ou sans optimisation garantissant une borne inférieure sur la priorité minimale, car chaque sommet est trouvé en un temps proportionnel à son degré et la somme des degrés de tous les sommets est linéaire par rapport au nombre d'arêtes du graphe.
L'algorithme de Dial pour les chemins les plus courts
Dans l'algorithme de Dijkstra pour la recherche des plus courts chemins dans les graphes orientés dont les poids des arêtes sont des entiers positifs, les priorités sont monotones , et une file d'attente à compartiments monotone permet d'obtenir une complexité temporelle de algorithme de Dial , du nom de Robert B. Dial, qui l'a publié en 1969 Le même principe s'applique également, avec une file d'attente à compartiments quantifiée, aux graphes dont les poids des arêtes sont des nombres réels positifs, lorsque le rapport entre le poids maximal et le poids minimal est inférieur ou égal à problème du chemin le plus large . Combinée à des méthodes permettant de partitionner rapidement les poids non entiers des arêtes en sous-ensembles auxquels on peut attribuer des priorités entières, elle conduit à des solutions en temps quasi linéaire pour la version à source unique et destination unique du problème du chemin le plus large.
Couverture de l'ensemble Greedy
Le problème de la couverture d'ensembles prend en entrée une famille d'ensembles . La sortie doit être une sous-famille de ces ensembles, ayant la même union que la famille originale et contenant le moins d'ensembles possible. Ce problème est NP-difficile , mais admet un algorithme d'approximation glouton qui atteint un facteur d'approximation logarithmique, soit le meilleur possible sauf si P = NP . Cet algorithme sélectionne sa sous-famille en choisissant itérativement un ensemble qui couvre le maximum d'éléments non couverts restants. Un exercice classique de conception d'algorithmes consiste à implémenter cet algorithme en temps linéaire par rapport à la taille de l'entrée, qui est la somme des tailles de tous les ensembles d'entrée.
Ce problème peut être résolu à l'aide d'une file d'attente de compartiments contenant des ensembles de la famille d'entrée, classés par ordre de priorité selon le nombre d'éléments restants qu'ils couvrent. À chaque fois que l'algorithme glouton choisit un ensemble pour sa sortie, les éléments de cet ensemble nouvellement couvert sont soustraits des priorités des autres ensembles qui les couvrent. Au cours de l'algorithme, le nombre de ces changements de priorité est égal à la somme des tailles des ensembles d'entrée. Les priorités sont des entiers décroissants, majorés par le nombre d'éléments à couvrir. Chaque choix de l'algorithme glouton consiste à trouver l'ensemble de priorité maximale, ce qui peut être réalisé en parcourant les compartiments de la file d'attente, en commençant par la valeur maximale précédente la plus récente. La complexité temporelle totale est linéaire par rapport à la taille de l'entrée.
Planification
Les files d'attente à compartiments peuvent être utilisées pour planifier des tâches avec des échéances, par exemple pour le transfert de paquets de données Internet avec garanties de qualité de service . Dans ce cas, les échéances doivent être quantifiées en intervalles discrets, et les tâches dont les échéances se situent dans le même intervalle sont considérées comme ayant une priorité équivalente.
Une variante de la structure de données de file d'attente à compartiments quantifiés, appelée file d'attente calendaire , a été appliquée à la planification de simulations à événements discrets . Dans cette file d'attente, les éléments sont des événements futurs, priorisés selon leur échéance temporelle au sein de la simulation. L'ordre des événements étant crucial dans cette application, les priorités ne peuvent être approximatives. Par conséquent, la file d'attente calendaire effectue la recherche de l'élément de priorité minimale différemment d'une file d'attente à compartiments : alors que cette dernière peut renvoyer n'importe quel élément du premier compartiment non vide, la file d'attente calendaire parcourt tous les éléments de ce compartiment pour déterminer celui qui possède la plus petite priorité non quantifiée. Afin d'optimiser la rapidité de ces recherches, cette variante s'efforce de maintenir un nombre de compartiments proportionnel au nombre d'éléments, en ajustant le niveau de quantification et en reconstruisant la structure de données lorsqu'elle se déséquilibre. Les files d'attente calendaires peuvent être plus lentes que les files d'attente à compartiments dans le pire des cas (lorsque de nombreux éléments se retrouvent dans le même compartiment de plus petite taille), mais elles sont rapides lorsque les éléments sont uniformément répartis entre les compartiments, ce qui garantit une taille moyenne de compartiment constante.
marche rapide
En mathématiques appliquées et en méthodes numériques pour la résolution d' équations différentielles , des files de priorité non ordonnées ont été utilisées pour prioriser les étapes de la méthode de propagation rapide (fast marching) pour la résolution des problèmes aux limites de l' équation eikonale , utilisée pour modéliser la propagation des ondes . Cette méthode détermine les instants où une frontière mobile traverse un ensemble de points discrets (tels que les points d'une grille entière) à l'aide d'une méthode de priorisation semblable à une version continue de l' algorithme de Dijkstra . Son temps d'exécution est dominé par la file de priorité de ces points. Il est possible d'accélérer la méthode jusqu'à un temps linéaire en arrondissant les priorités utilisées dans cet algorithme à des entiers, et en utilisant une file à compartiments pour ces entiers. Comme dans les algorithmes de Dijkstra et de Dial, les priorités sont monotones ; la méthode de propagation rapide peut donc exploiter l'optimisation monotone de la file à compartiments et son analyse. Cependant, la discrétisation introduit une erreur dans les calculs résultants.