file d'attente à priorité monotone

En informatique , une file de priorité monotone est une variante du type de données abstrait de file de priorité dans laquelle les priorités des éléments extraits doivent former une séquence monotone . Autrement dit, pour une file de priorité où chaque élément extrait successivement est celui de priorité minimale (un tas min), la priorité minimale doit être croissante. Inversement, pour un tas max, la priorité maximale doit être décroissante. L'hypothèse de monotonie apparaît naturellement dans plusieurs applications des files de priorité et peut être utilisée comme simplification pour accélérer certains types de files de priorité.

Une condition nécessaire et suffisante pour une file d'attente à priorité monotone est qu'on ne tente jamais d'ajouter un élément de priorité inférieure à celle de l'élément extrait le plus récemment.

Les files d'attente à priorité monotone apparaissent naturellement lorsqu'on ordonne des événements chronologiquement, comme les délais d'attente réseau ou la simulation d'événements discrets . Un événement peut déclencher la planification d'une action ultérieure, mais la causalité (réelle ou simulée) rend vaine toute tentative de planification d'actions passées.

Dans l'algorithme de Dijkstra pour le problème du plus court chemin , les sommets d'un graphe pondéré donné sont extraits par ordre croissant de distance au sommet de départ, et une file de priorité est utilisée pour déterminer le sommet restant le plus proche du sommet de départ. Par conséquent, dans cette application, les opérations sur la file de priorité sont monotones.

De même, dans les algorithmes de balayage de lignes en géométrie algorithmique , les événements où la ligne de balayage croise un point d'intérêt sont priorisés par les coordonnées du point traversé, et ces événements sont extraits selon un ordre monotone. Un ordre d'extraction monotone se retrouve également dans la version « meilleur d'abord » de l' algorithme de séparation et d'évaluation .

Toute file de priorité capable de gérer des extractions non monotones peut également gérer des extractions monotones. Cependant, certaines files de priorité sont spécialisées pour fonctionner uniquement avec des extractions monotones, ou fonctionnent mieux lorsque les extractions sont monotones. Par exemple, la file de priorité à compartiments est une structure de données simple composée d'un tableau indexé par priorité, où chaque cellule du tableau contient un compartiment d'éléments ayant cette priorité. Une opération d'extraction minimale effectue une recherche séquentielle du premier compartiment non vide et choisit un élément arbitraire dans ce compartiment. Pour les extractions non monotones, chaque opération d'extraction minimale prend un temps (dans le pire des cas) proportionnel à la longueur du tableau (le nombre de priorités distinctes). Cependant, lorsqu'elle est utilisée comme file de priorité monotone, la recherche du prochain compartiment non vide peut commencer à la priorité de la dernière opération d'extraction minimale effectuée, plutôt qu'au début du tableau. Cette optimisation fait que le temps total d'une séquence d'opérations est proportionnel à la somme du nombre d'opérations et de la longueur du tableau, au lieu d'être (comme dans le cas non monotone) le produit de ces deux quantités.

un temps amorti.par opération d'extraction minimale. Une autre structure apparentée de [ Ces résultats conduisent à une accélération correspondante dans l'algorithme de Dijkstra pour les graphes avec des poids d'arêtes entiers