File d'attente de priorité - Priority queue

En informatique , une file d'attente prioritaire est un type de données abstrait similaire à une file d'attente régulière ou à une structure de données de pile dans laquelle chaque élément a en plus une "priorité" qui lui est associée. Dans une file d'attente prioritaire, un élément de haute priorité est servi avant un élément de faible priorité. Dans certaines implémentations, si deux éléments ont la même priorité, ils sont servis selon l'ordre dans lequel ils ont été mis en file d'attente, tandis que dans d'autres implémentations, l'ordre des éléments avec la même priorité n'est pas défini.

Alors que les files d'attente prioritaires sont souvent implémentées avec des tas , elles sont conceptuellement distinctes des tas. Une file d'attente prioritaire est un concept comme « une liste » ou « une carte » ; tout comme une liste peut être implémentée avec une liste chaînée ou un tableau , une file d'attente prioritaire peut être implémentée avec un tas ou une variété d'autres méthodes telles qu'un tableau non ordonné.

Opérations

Une file d'attente prioritaire doit au moins prendre en charge les opérations suivantes :

is_empty : vérifie si la file d'attente n'a pas d'éléments.
insert_with_priority : ajoute un élément à la file d' attente avec une priorité associée.
pull_highest_priority_element : supprime l'élément de la file d'attente qui a la priorité la plus élevée et le renvoie.

Ceci est également connu sous le nom de " pop_element(Off) ", " get_maximum_element " ou " get_front(most)_element ".

Certaines conventions inversent l'ordre des priorités, considérant que les valeurs inférieures sont prioritaires, ce qui peut également être appelé " get_minimum_element ", et est souvent appelé " get-min " dans la littérature.

Cela peut à la place être spécifié en tant que fonctions distinctes " peek_at_highest_priority_element " et " delete_element ", qui peuvent être combinées pour produire " pull_highest_priority_element ".

De plus, peek (souvent appelé dans ce contexte find-max ou find-min ), qui renvoie l'élément de priorité la plus élevée mais ne modifie pas la file d'attente, est très fréquemment implémenté et s'exécute presque toujours en temps O (1) . Cette opération et ses performances O (1) sont cruciales pour de nombreuses applications de files d'attente prioritaires.

Des implémentations plus avancées peuvent prendre en charge des opérations plus compliquées, telles que pull_lowest_priority_element , inspecter les premiers éléments de priorité la plus élevée ou la plus faible, effacer la file d'attente, effacer des sous-ensembles de la file d'attente, effectuer une insertion par lots, fusionner deux ou plusieurs files d'attente en une, incrémenter la priorité de tout élément, etc.

Les piles et les files d'attente sont différentes des files d'attente prioritaires. Dans une file d'attente prioritaire, l'ordre est intrinsèque : il dépend de la valeur insérée. Dans une pile ou une file d'attente, l'ordre est extrinsèque : il dépend de l'ordre dans lequel la valeur est insérée. En termes de sous - typage comportemental , une file d'attente n'est pas un sous-type d'une file d'attente prioritaire et une file d'attente prioritaire n'est pas un sous-type d'une file d'attente. Ni l'un ni l'autre ne peut se substituer à l'autre, ni l'un ou l'autre ne doit être un sous-type de l'autre dans une hiérarchie d'héritage .

Mise en œuvre

Implémentations naïves

Il existe une variété de façons simples, généralement inefficaces, de mettre en œuvre une file d'attente prioritaire. Ils fournissent une analogie pour aider à comprendre ce qu'est une file d'attente prioritaire.

Par exemple, on peut garder tous les éléments dans une liste non triée ( O (1) temps d'insertion). Chaque fois que l'élément de priorité la plus élevée est demandé, recherchez dans tous les éléments celui qui a la priorité la plus élevée. ( O ( n ) temps d'extraction),

insert(node) {
  list.append(node)
}

pull() {
  highest = list.get_first_element()
  foreach node in list {
     if highest.priority < node.priority {
         highest = node
     }
  }
  list.remove(highest)
  return highest
}

Dans un autre cas, on peut garder tous les éléments dans une liste triée par priorité ( O (n) temps de tri par insertion), chaque fois que l'élément le plus prioritaire est demandé, le premier de la liste peut être retourné. ( O (1) temps de traction)

insert(node) {
  highest = list.get_first_element()
  foreach (index, element) in list {
    if node.priority < element.priority {
       list.insert_at_index(node,index)
    }
  }
}

pull() {
    highest = list.get_at_index(list.length-1)
    list.remove(highest)
    return highest
}

Mise en œuvre habituelle

Pour améliorer les performances, les files d'attente prioritaires sont généralement basées sur un tas , donnant des performances O (log n ) pour les insertions et les suppressions, et O ( n ) pour construire le tas initialement à partir d'un ensemble de n éléments. Des variantes de la structure de données de tas de base, telles que les tas d'appariement ou les tas de Fibonacci, peuvent fournir de meilleures limites pour certaines opérations.

Alternativement, lorsqu'un arbre de recherche binaire auto-équilibré est utilisé, l'insertion et la suppression prennent également O (log n ) temps, bien que la construction d'arbres à partir de séquences d'éléments existantes prenne O ( n log n ) temps ; ceci est typique lorsque l'on peut déjà avoir accès à ces structures de données, comme avec des bibliothèques tierces ou standard. Du point de vue de la complexité de l'espace, l'utilisation d' un arbre de recherche binaire à équilibrage automatique avec une liste chaînée prend plus de stockage, car elle nécessite de stocker des références supplémentaires vers d'autres nœuds.

Du point de vue de la complexité de calcul, les files d'attente prioritaires sont conformes aux algorithmes de tri. La section sur l'équivalence des files d'attente prioritaires et des algorithmes de tri , ci-dessous, décrit comment des algorithmes de tri efficaces peuvent créer des files d'attente prioritaires efficaces.

Tas spécialisés

Il existe plusieurs structures de données de tas spécialisées qui fournissent des opérations supplémentaires ou surpassent les implémentations basées sur des tas pour des types spécifiques de clés, en particulier des clés entières. Supposons que l'ensemble des clés possibles soit {1, 2, ..., C}.

Lorsque seuls insert , find-min et extract-min sont nécessaires et en cas de priorités entières, une file d'attente de seau peut être construite sous la forme d'un tableau de listes chaînées $C$ plus un pointeur $top$ , initialement $C$ . L'insertion d'un élément avec la clé $k$ ajoute l'élément au $k$ 'ème et met à jour $top \leftarrow min(top,$ $k$ $)$ , les deux en temps constant. Extract-min supprime et renvoie un élément de la liste avec l'index $top$ , puis incrémente $top$ si nécessaire jusqu'à ce qu'il pointe à nouveau vers une liste non vide ; cela prend du temps $O$ $($ $C$ $)$ dans le pire des cas. Ces files d'attente sont utiles pour trier les sommets d'un graphe par leur degré.
Un arbre de van Emde Boas prend en charge les opérations minimum , maximum , insert , delete , search , extract-min , extract-max , prédécesseur et successeur en temps O (log log C ), mais a un coût d'espace pour les petites files d'attente d'environ O ( 2 ^{m /2} ), où m est le nombre de bits dans la valeur de priorité. L'espace peut être considérablement réduit avec le hachage.
L' arbre Fusion de Fredman et Willard implémente l' opération minimale en temps O (1) et les opérations d' insertion et d' extraction min en temps. Cependant, il est déclaré par l'auteur que "Nos algorithmes n'ont qu'un intérêt théorique ; les facteurs constants impliqués dans les temps d'exécution excluent l'aspect pratique." $O(\log n/\log \log C)$

Pour les applications qui effectuent de nombreuses opérations " peek " pour chaque opération "extract-min", la complexité temporelle des actions peek peut être réduite à O (1) dans toutes les implémentations d'arborescence et de tas en mettant en cache l'élément de priorité la plus élevée après chaque insertion et suppression. Pour l'insertion, cela ajoute au maximum un coût constant, puisque l'élément nouvellement inséré n'est comparé qu'à l'élément minimum précédemment mis en cache. Pour la suppression, cela ajoute tout au plus un coût de "coup d'œil" supplémentaire, qui est généralement moins cher que le coût de suppression, de sorte que la complexité temporelle globale n'est pas significativement affectée.

Les files d'attente à priorité monotone sont des files d'attente spécialisées optimisées pour le cas où aucun élément n'est jamais inséré qui a une priorité inférieure (dans le cas de min-heap) que tout élément précédemment extrait. Cette restriction est satisfaite par plusieurs applications pratiques des files d'attente prioritaires.

Résumé des temps de parcours

Voici les complexités temporelles de diverses structures de données de tas. Les noms de fonction supposent un tas min. Pour la signification de " O ( f )" et " Θ ( f )" voir la notation Big O .

Opération	trouver-min	supprimer-min	insérer	touche-diminution	fusionner
Binaire	Θ (1)	Θ (log n )	O (log n )	O (log n )	Θ ( n )
Gauchiste	Θ (1)	Θ (log n )	Θ (log n )	O (log n )	Θ (log n )
Binôme	Θ (1)	Θ (log n )	Θ (1)	Θ (log n )	O (log n )
Fibonacci	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Jumelage	Θ (1)	O (log n )	Θ (1)	o (log n )	Θ (1)
Brodal	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Jumelage de rangs	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Fibonacci strict	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
2-3 tas	O (log n )	O (log n )	O (log n )	Θ (1)	?

Équivalence des files d'attente prioritaires et des algorithmes de tri

Utiliser une file d'attente prioritaire pour trier

La sémantique des files prioritaires suggère naturellement une méthode de tri : insérer tous les éléments à trier dans une file prioritaire, et les supprimer séquentiellement ; ils sortiront dans l'ordre trié. C'est en fait la procédure utilisée par plusieurs algorithmes de tri , une fois la couche d' abstraction fournie par la file d'attente prioritaire supprimée. Cette méthode de tri est équivalente aux algorithmes de tri suivants :

Nom	Implémentation de file d'attente prioritaire	Meilleur	Moyenne	Pire
Tri en tas	Tas	${\style d'affichage n\log(n)}$	${\style d'affichage n\log(n)}$	${\style d'affichage n\log(n)}$
Tri lisse	Léonard Tas	${\style d'affichage n}$	${\style d'affichage n\log(n)}$	${\style d'affichage n\log(n)}$
Tri par sélection	Tableau non ordonné	${\style d'affichage n^{2}}$	${\style d'affichage n^{2}}$	${\style d'affichage n^{2}}$
Tri par insertion	Tableau commandé	${\style d'affichage n}$	${\style d'affichage n^{2}}$	${\style d'affichage n^{2}}$
Tri de l'arbre	Arbre de recherche binaire auto-équilibré	${\style d'affichage n\log(n)}$	${\style d'affichage n\log(n)}$	${\style d'affichage n\log(n)}$

Utiliser un algorithme de tri pour créer une file d'attente prioritaire

Un algorithme de tri peut également être utilisé pour implémenter une file d'attente prioritaire. Plus précisément, Thorup dit :

Nous présentons une réduction d'espace linéaire déterministe générale des files d'attente prioritaires au tri impliquant que si nous pouvons trier jusqu'à n clés en S ( n ) temps par clé, alors il existe une file d'attente prioritaire prenant en charge la suppression et l' insertion en O ( S ( n )) time et find-min en temps constant.

C'est-à-dire que s'il existe un algorithme de tri qui peut trier en un temps O ( S ) par clé, où S est une fonction de n et de la taille du mot , alors on peut utiliser la procédure donnée pour créer une file d'attente prioritaire où tirer la priorité la plus élevée l'élément est le temps O (1), et l'insertion de nouveaux éléments (et la suppression des éléments) est le temps O ( S ). Par exemple, si l'on a un algorithme de tri O ( n log n ), on peut créer une file d'attente prioritaire avec O (1) tirant et O (n log n ) insertion.

Bibliothèques

Une file d'attente prioritaire est souvent considérée comme une " structure de données de conteneur ".

La bibliothèque de modèles standard (STL) et la norme C++ 1998, spécifient std::priority_queue comme l'un des modèles de classe d' adaptateur de conteneur STL . Cependant, il ne spécifie pas comment deux éléments de même priorité doivent être servis, et en effet, les implémentations courantes ne les renverront pas en fonction de leur ordre dans la file d'attente. Il implémente une file d'attente max-priority et a trois paramètres : un objet de comparaison pour le tri tel qu'un objet de fonction (par défaut à less<T> si non spécifié), le conteneur sous-jacent pour stocker les structures de données (par défaut à std::vector <T>), et deux itérateurs au début et à la fin d'une séquence. Contrairement aux conteneurs STL réels, il ne permet pas l' itération de ses éléments (il adhère strictement à sa définition de type de données abstrait). STL a également des fonctions utilitaires pour manipuler un autre conteneur à accès aléatoire comme un max-heap binaire. Les bibliothèques Boost ont également une implémentation dans le tas de bibliothèque.

Le module heapq de Python implémente un min-heap binaire en haut d'une liste.

La bibliothèque Java contient une PriorityQueueclasse qui implémente une file d'attente min-priority.

La bibliothèque de Scala contient une classe PriorityQueue , qui implémente une file d'attente max-priority.

La bibliothèque de Go contient un module conteneur/tas , qui implémente un min-heap au-dessus de toute structure de données compatible.

L' extension Standard PHP Library contient la classe SplPriorityQueue .

Le framework Core Foundation d' Apple contient une structure CFBinaryHeap , qui implémente un min-heap.

Applications

Gestion de la bande passante

La file d'attente prioritaire peut être utilisée pour gérer des ressources limitées telles que la bande passante sur une ligne de transmission à partir d'un routeur réseau . En cas de file d'attente du trafic sortant en raison d'une bande passante insuffisante, toutes les autres files d'attente peuvent être interrompues pour envoyer le trafic de la file d'attente la plus prioritaire à l'arrivée. Cela garantit que le trafic prioritaire (comme le trafic en temps réel, par exemple un flux RTP d'une connexion VoIP ) est transmis avec le moins de retard et le moins de chances d'être rejeté en raison d'une file d'attente atteignant sa capacité maximale. Tout le reste du trafic peut être traité lorsque la file d'attente la plus prioritaire est vide. Une autre approche utilisée consiste à envoyer plus de trafic de manière disproportionnée à partir de files d'attente de priorité plus élevée.

De nombreux protocoles modernes pour les réseaux locaux incluent également le concept de files d'attente prioritaires au niveau de la sous-couche de contrôle d'accès au support (MAC) pour garantir que les applications hautement prioritaires (telles que VoIP ou IPTV ) connaissent une latence inférieure à celle des autres applications pouvant être servies avec meilleur service d' effort . Les exemples incluent IEEE 802.11e (un amendement à IEEE 802.11 qui fournit une qualité de service ) et ITU-T G.hn (une norme pour les réseaux locaux à haut débit utilisant le câblage domestique existant ( lignes électriques, lignes téléphoniques et câbles coaxiaux ).

Habituellement, une limitation (policier) est définie pour limiter la bande passante que le trafic de la file d'attente la plus prioritaire peut prendre, afin d'empêcher les paquets de haute priorité d'étouffer tout le reste du trafic. Cette limite n'est généralement jamais atteinte en raison d'instances de contrôle de haut niveau telles que Cisco Callmanager , qui peuvent être programmées pour inhiber les appels qui dépasseraient la limite de bande passante programmée.

Simulation d'événements discrets

Une autre utilisation d'une file d'attente prioritaire est de gérer les événements dans une simulation d'événements discrets . Les événements sont ajoutés à la file d'attente avec leur temps de simulation utilisé comme priorité. L'exécution de la simulation se déroule en tirant à plusieurs reprises le haut de la file d'attente et en exécutant l'événement sur celui-ci.

Voir aussi : Ordonnancement (informatique) , théorie des files d'attente

L'algorithme de Dijkstra

Lorsque le graphe est stocké sous la forme d' une liste ou d'une matrice d' adjacence , la file d'attente prioritaire peut être utilisée pour extraire efficacement le minimum lors de la mise en œuvre de l'algorithme de Dijkstra , bien qu'il faille également pouvoir modifier efficacement la priorité d'un sommet particulier dans la file d'attente prioritaire.

Si à la place, un graphe est stocké en tant qu'objets nœuds et que des paires de nœuds prioritaires sont insérées dans un tas, il n'est pas nécessaire de modifier la priorité d'un sommet particulier si l'on suit les nœuds visités. Une fois qu'un nœud est visité, s'il réapparaît dans le tas (ayant eu un numéro de priorité inférieur associé plus tôt), il est supprimé et ignoré.

Codage de Huffman

Le codage de Huffman nécessite l'obtention répétée des deux arbres de fréquence la plus basse. Une file d'attente prioritaire est une méthode pour ce faire .

Algorithmes de recherche du meilleur premier

Les algorithmes de recherche Best- First, comme l' algorithme de recherche A* , trouvent le chemin le plus court entre deux sommets ou nœuds d'un graphe pondéré , en essayant d'abord les routes les plus prometteuses. Une file d'attente prioritaire (également connue sous le nom de frange ) est utilisée pour garder une trace des routes inexplorées ; celui pour lequel l'estimation (une borne inférieure dans le cas de A*) de la longueur totale du trajet est la plus petite reçoit la priorité la plus élevée. Si les limitations de mémoire rendent la recherche du meilleur premier impossible, des variantes telles que l' algorithme SMA* peuvent être utilisées à la place, avec une file d' attente prioritaire à deux extrémités pour permettre la suppression des éléments de faible priorité.

Algorithme de triangulation ROAM

L' algorithme Real-time Optimally Adapting Meshes ( ROAM ) calcule une triangulation dynamiquement changeante d'un terrain. Cela fonctionne en divisant les triangles là où plus de détails sont nécessaires et en les fusionnant là où moins de détails sont nécessaires. L'algorithme attribue à chaque triangle du terrain une priorité, généralement liée à la diminution de l'erreur si ce triangle était divisé. L'algorithme utilise deux files d'attente prioritaires, une pour les triangles pouvant être divisés et une autre pour les triangles pouvant être fusionnés. À chaque étape, le triangle de la file d'attente divisée avec la priorité la plus élevée est divisé, ou le triangle de la file d'attente de fusion avec la priorité la plus faible est fusionné avec ses voisins.

Algorithme de Prim pour l'arbre couvrant minimal

En utilisant la file d'attente de priorité de tas min dans l'algorithme de Prim pour trouver l' arbre couvrant minimal d'un graphe connecté et non orienté , on peut obtenir un bon temps d'exécution. Cette file d'attente de priorité de tas min utilise la structure de données de tas min qui prend en charge des opérations telles que insert , minimum , extract-min , reduce-key . Dans cette implémentation, le poids des arêtes est utilisé pour décider de la priorité des sommets . Diminuez le poids, augmentez la priorité et augmentez le poids, diminuez la priorité.

File d'attente prioritaire parallèle

La parallélisation peut être utilisée pour accélérer les files d'attente prioritaires, mais nécessite quelques modifications de l'interface de file d'attente prioritaire. La raison de ces changements est qu'une mise à jour séquentielle a généralement ou coût, et il n'y a pas de gain pratique pour paralléliser une telle opération. Une modification possible consiste à autoriser l'accès simultané de plusieurs processeurs à la même file d'attente prioritaire. Le deuxième changement possible est d'autoriser les opérations par lots qui fonctionnent sur des éléments, au lieu d'un seul élément. Par exemple, extractMin supprimera les premiers éléments ayant la priorité la plus élevée. ${\textstyle O(1)}$ ${\textstyle O(\log n)}$ ${\textstyle k}$ ${\textstyle k}$

Accès parallèle simultané

Si la file d'attente prioritaire autorise un accès simultané, plusieurs processus peuvent effectuer des opérations simultanément sur cette file d'attente prioritaire. Cependant, cela soulève deux problèmes. Tout d'abord, la définition de la sémantique des opérations individuelles n'est plus évidente. Par exemple, si deux processus veulent extraire l'élément avec la priorité la plus élevée, doivent-ils obtenir le même élément ou des éléments différents ? Cela limite le parallélisme au niveau du programme utilisant la file d'attente prioritaire. De plus, étant donné que plusieurs processus ont accès au même élément, cela conduit à des conflits.

Le nœud 3 est inséré et définit le pointeur du nœud 2 sur le nœud 3. Immédiatement après cela, le nœud 2 est supprimé et le pointeur du nœud 1 est défini sur le nœud 4. Maintenant, le nœud 3 n'est plus accessible.

L'accès simultané à une file d'attente prioritaire peut être mis en œuvre sur un modèle PRAM à lecture simultanée, écriture simultanée (CRCW). Dans ce qui suit, la file d'attente prioritaire est implémentée en tant que liste de sauts . De plus, une primitive de synchronisation atomique, CAS , est utilisée pour rendre la liste de sauts sans verrouillage . Les nœuds de la liste de saut se composent d'une clé unique, d'une priorité, d'un tableau de pointeurs , pour chaque niveau, vers les nœuds suivants et d'une marque de suppression . La marque de suppression indique si le nœud est sur le point d'être supprimé par un processus. Cela garantit que les autres processus peuvent réagir de manière appropriée à la suppression.

insert(e) : Tout d'abord, un nouveau nœud avec une clé et une priorité est créé. De plus, le nœud se voit attribuer un certain nombre de niveaux, ce qui dicte la taille du tableau de pointeurs. Ensuite, une recherche est effectuée pour trouver la position correcte où insérer le nouveau nœud. La recherche commence à partir du premier nœud et du niveau le plus élevé. Ensuite, la liste de sauts est parcourue jusqu'au niveau le plus bas jusqu'à ce que la position correcte soit trouvée. Pendant la recherche, pour chaque niveau, le dernier nœud traversé sera enregistré comme nœud parent pour le nouveau nœud à ce niveau. De plus, le nœud vers lequel pointe le pointeur, à ce niveau, du nœud parent, sera enregistré en tant que nœud successeur du nouveau nœud à ce niveau. Ensuite, pour chaque niveau du nouveau nœud, les pointeurs du nœud parent seront définis sur le nouveau nœud. Enfin, les pointeurs, pour chaque niveau, du nouveau nœud seront définis sur les nœuds successeurs correspondants.
extract-min : Tout d'abord, la liste de sauts est parcourue jusqu'à ce qu'un nœud soit atteint dont la marque de suppression n'est pas définie. Cette marque de suppression est alors définie sur true pour ce nœud. Enfin, les pointeurs des nœuds parents du nœud supprimé sont mis à jour.

Si l'accès concurrent à une file d'attente prioritaire est autorisé, des conflits peuvent survenir entre deux processus. Par exemple, un conflit survient si un processus essaie d'insérer un nouveau nœud, mais qu'en même temps un autre processus est sur le point de supprimer le prédécesseur de ce nœud. Il existe un risque que le nouveau nœud soit ajouté à la liste de sauts, mais il n'est plus accessible. ( Voir photo )

Opérations des éléments K

Dans ce cadre, les opérations sur une file d'attente prioritaire sont généralisées à un lot d' éléments. Par exemple, k_extract-min supprime les plus petits éléments de la file d'attente prioritaire et les renvoie. ${\textstyle k}$ ${\textstyle k}$

Dans un paramètre de mémoire partagée , la file d'attente de priorité parallèle peut être facilement implémentée à l'aide d' arbres de recherche binaires parallèles et d'algorithmes d'arbres basés sur les jointures . En particulier, k_extract-min correspond à une scission sur l'arbre de recherche binaire qui a un coût et donne un arbre qui contient les plus petits éléments. k_insert peut être appliqué par une union de la file d'attente prioritaire d'origine et du lot d'insertions. Si le lot est déjà trié par clé, k_insert a un coût. Sinon, nous devons d'abord trier le lot, donc le coût sera de . D'autres opérations pour la file d'attente prioritaire peuvent être appliquées de la même manière. Par exemple, k_decrease-key peut être effectué en appliquant d'abord la différence puis l' union , qui supprime d'abord les éléments, puis les réinsère avec les clés mises à jour. Toutes ces opérations sont très parallèles, et l'efficacité théorique et pratique peut être trouvée dans les documents de recherche connexes. ${\textstyle O(\log n)}$ ${\textstyle k}$ ${\textstyle O(k\log(1+{\frac {n}{k}}))}$ ${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$

Le reste de cette section traite d'un algorithme basé sur la file d'attente sur la mémoire distribuée. Nous supposons que chaque processeur a sa propre mémoire locale et une file d'attente de priorité locale (séquentielle). Les éléments de la file d'attente prioritaire globale (parallèle) sont répartis sur tous les processeurs.

k_extract-min est exécuté sur une file d'attente prioritaire avec trois processeurs. Les éléments verts sont renvoyés et supprimés de la file d'attente prioritaire.

Une opération k_insert attribue les éléments uniformément aléatoires aux processeurs qui insèrent les éléments dans leurs files d'attente locales. Notez que des éléments uniques peuvent toujours être insérés dans la file d'attente. En utilisant cette stratégie, les plus petits éléments globaux sont dans l'union des plus petits éléments locaux de chaque processeur avec une probabilité élevée. Ainsi, chaque processeur détient une partie représentative de la file d'attente prioritaire globale.

Cette propriété est utilisée lorsque k_extract-min est exécuté, car les plus petits éléments de chaque file d'attente locale sont supprimés et collectés dans un ensemble de résultats. Les éléments du jeu de résultats sont toujours associés à leur processeur d'origine. Le nombre d'éléments supprimés de chaque file d'attente locale dépend du nombre de processeurs et de celui-ci . Par sélection parallèle, les plus petits éléments de l'ensemble de résultats sont déterminés. Avec une forte probabilité, ce sont les plus petits éléments mondiaux . Sinon, les éléments sont à nouveau supprimés de chaque file d'attente locale et placés dans l'ensemble de résultats. Ceci est fait jusqu'à ce que les plus petits éléments globaux soient dans le jeu de résultats. Maintenant, ces éléments peuvent être retournés. Tous les autres éléments du jeu de résultats sont réinsérés dans leurs files d'attente locales. Le temps d' exécution de k_extract-min est attendu , où et est la taille de la file d'attente prioritaire. ${\textstyle m}$ ${\textstyle m}$ ${\textstyle k}$ ${\textstyle p}$ ${\textstyle k}$ ${\textstyle k}$ ${\textstyle m}$ ${\textstyle k}$ ${\textstyle k}$ ${\textstyle O({\frac {k}{p}}\log(n))}$ ${\textstyle k=\Omega (p\cdot \log(p))}$ ${\styletexte n}$

La file d'attente prioritaire peut être encore améliorée en ne déplaçant pas les éléments restants du jeu de résultats directement dans les files d'attente locales après une opération k_extract-min . Cela évite de déplacer des éléments dans les deux sens entre le jeu de résultats et les files d'attente locales.

En supprimant plusieurs éléments à la fois, une accélération considérable peut être atteinte. Mais tous les algorithmes ne peuvent pas utiliser ce type de file d'attente prioritaire. L'algorithme de Dijkstra par exemple ne peut pas fonctionner sur plusieurs nœuds à la fois. L'algorithme prend le nœud le plus éloigné de la file d'attente prioritaire et calcule de nouvelles distances pour tous ses nœuds voisins. Si vous supprimiez des nœuds, travailler sur un nœud pourrait changer la distance d'un autre des nœuds. Ainsi, l'utilisation d'opérations d'éléments k détruit la propriété de définition d'étiquette de l'algorithme de Dijkstra. ${\textstyle k}$ ${\textstyle k}$

Voir également

Les références

Lectures complémentaires

Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Section 6.5 : Files d'attente prioritaires". Introduction aux algorithmes (2e éd.). MIT Press et McGraw-Hill. p. 138-142. ISBN 0-262-03293-7.

Liens externes

Référence C++ pour std::priority_queue
Descriptions de Lee Killough
PQlib - Bibliothèque de file d'attente prioritaire open source pour C
libpqueue est une implémentation générique de file d'attente prioritaire (heap) (en C) utilisée par le projet Apache HTTP Server.
Enquête sur les structures de file d'attente prioritaires connues par Stefan Xenos
UC Berkeley - Computer Science 61B - Conférence 24: Priority Queues (vidéo) - introduction aux files d'attente prioritaires utilisant un tas binaire

Languages

In other projects