Facile d'utilisation min de file d'attente de priorité avec la mise à jour de clé en C++

Bien, comme Darren déjà dit, std::priority_queue n'en avons pas les moyens pour diminuer la priorité d'un élément, et ni la suppression d'un élément autre que le courant min. Mais le défaut std::priority_queue n'est rien de plus qu'un simple conteneur de l'adaptateur autour d'un std::vector qui utilise le std tas de fonctions de <algorithm> (std::push_heap, std::pop_heap et std::make_heap). Donc, pour Dijkstra (où vous avez besoin de la priorité de mise à jour) j'ai l'habitude de faire ça moi-même et d'utiliser un simple std::vector.

Un push est alors en O(log N) opérations de

vec.push_back(item);
std::push_heap(vec.begin(), vec.end());

De cours pour la construction d'une file d'attente à nouveau à partir de N éléments, nous ne poussent pas tous en utilisant cette O(log N) opération (ce qui rend la chose entière O(Nlog N)) mais juste de les mettre tous dans le vecteur suivie par une simple O(N)

std::make_heap(vec.begin(), vec.end());

Min élément est un simple O(1)

vec.front();

Une pop qui est la simple O(log N) séquence

std::pop_heap(vec.begin(), vec.end());
vec.pop_back();

Jusqu'à présent c'est tout ce que std::priority_queue fait habituellement sous le capot. Maintenant, pour modifier un élément prioritaire de la nous avons juste besoin de le changer (mais il peut être incorporé dans le type de l'élément) et de faire la séquence valide d'un tas de nouveau

std::make_heap(vec.begin(), vec.end());

Je sais que c'est un O(N) opérations, mais d'un autre côté cela supprime toute nécessité de garder une trace de la position d'un enregistrement dans le tas avec une structure de données supplémentaires ou (pire encore) une augmentation des éléments de type. Et la dégradation des performances sur une échelle logarithmique de la mise à jour prioritaire est pas, en pratique, que des importants, compte tenu de la facilité d'utilisation, compact et linéaire de la mémoire useage de std::vector (qui a des répercussions de l'exécution, aussi), et le fait que j'ai souvent travailler avec des graphiques qui ont assez peu d'arêtes (linéaire en le nombre de sommets) de toute façon.

Il ne peut pas dans tous les cas, le moyen le plus rapide, mais certainement le plus simple.

EDIT: Oh, et depuis la bibliothèque standard utilise max-tas, vous devez utiliser un équivalent de > pour comparer les priorités (cependant vous les obtenir à partir des éléments), au lieu de la valeur par défaut < opérateur.

Je ne pense pas que le std::priority_queue classe permet une mise en œuvre efficace de decrease-key opérations de style.

J'ai roulé ma propre tas binaire basée sur la structure de données qui prend en charge ce, bascially très similaire à ce que vous avez décrit pour la std::set en fonction de la priorité de la file d'attente que vous avez:

• Maintenir un tas binaire, triés par value qui stocke les éléments de pair<value, ID> et un tableau de cartes ID -> heap_index. Dans le tas de routines heapify_up, heapify_down etc il est nécessaire de s'assurer que la cartographie tableau est conservé en synchronisation avec le courant tas position des éléments. Cela ajoute un peu d'extra O(1) frais généraux.
• Conversion d'un tableau à un segment peut être fait dans O(N) selon l'algorithme décrit ici.
• Jeter un oeil à l'élément racine est O(1).
• Vérifier si un ID est actuellement dans le tas, il suffit d'un O(1) de recherche dans le tableau de mappage. Cela permet également de O(1) jeter un oeil à l'élément correspondant à l'une ID.
• Decrease-key implique un O(1) de recherche dans le mappage d'un tableau, suivi par un O(log(N)) mise à jour le tas via heapify_up, heapify_down.
• Poussant un nouvel élément sur le tas est O(log(N)) comme le popping est une exitsing élément dans le tas.

Donc asymptotiquement le moteur d'exécution est amélioré pour un peu de l'exploitation par rapport à la std::set base de données de la structure. Une autre importante avancée est que le binaire tas peuvent être mis en œuvre sur un tableau, tandis que les arbres binaires sont basées sur les nœuds des conteneurs. Le supplément de la localité des données des tas binaire se traduit généralement par l'amélioration de l'exécution.

Quelques problèmes avec cette mise en œuvre sont:

• Il permet uniquement d'entiers élément ID's.
• Il suppose une étroite distribution de l'élément ID's, en commençant à zéro (autrement l'espace de la complexité de la cartographie de la matrice de coups!).

Vous pourriez potentiellement à surmonter ces problèmes, si vous avez maintenu un mappage de table de hachage, plutôt que d'une cartographie de réseau, mais avec un peu plus de gestion d'exécution. Pour mon utilisation, entier ID's ont toujours été assez.

Espère que cette aide.