Comment faire une mise à jour de priorité efficace dans STL priority_queue?

Question

J'ai une priorité_queue d'un objet:

typedef priority_queue<Object> Queue;
Queue queue;

De temps en temps, la priorité de l'un des objets peut changer - je dois pouvoir mettre à jour la priorité de cet objet dans la file d'attente de manière efficace. Actuellement, j'utilise cette méthode qui fonctionne mais semble inefficace:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

Je l’ai mis en place de cette façon parce que j’étais assez pressé à ce moment-là et c’était la chose la plus rapide que je pouvais faire pour pouvoir être sûr que tout fonctionnerait bien. Il doit y avoir un meilleur moyen que cela cependant. Vraiment ce que je veux, c’est un moyen d’être:

• extraire l'instance avec la priorité modifiée et en insérer une nouvelle avec la nouvelle valeur de priorité
• mettez à jour l'instance avec la priorité modifiée, puis mettez à jour la file d'attente afin qu'elle soit correctement triée

Quel est le meilleur moyen de le faire?

Answer 1

Je pense que vous n’avez pas de chance avec la file d’attente prioritaire standard, car vous ne pouvez pas accéder au répertoire / sous-vecteur / liste sous-jacent ou à d’autres activités. Vous devez mettre en œuvre votre propre projet - ce n’est pas si difficile.

Answer 2

Je peux suggérer deux solutions pour résoudre le problème, bien qu'aucune ne réalise une véritable mise à jour.

1. Utilisez la priority_queue et appuyez sur l'élément à chaque fois que vous souhaitez le mettre à jour. Acceptez le fait que vous aurez des entrées inutiles dans la file d'attente. Lorsque vous affichez la valeur supérieure, vérifiez si elle contient la valeur à jour. Sinon, ignorez-le et affichez le prochain.

   De cette façon, vous retardez la suppression de l'élément mis à jour jusqu'au sommet. J'ai remarqué que cette approche était utilisée par les plus grands programmeurs réalisant l'algorithme de Dijkstra.

2. Utilisez set . Il est également trié afin que vous puissiez extraire le plus grand élément en temps logarithmique. Vous pouvez également supprimer l'élément obsolète avant de l'insérer à nouveau. Donc, toujours pas d'opération de mise à jour possible, mais la suppression et la réinsertion sont possibles.

On dirait que la complexité des deux approches est la même.

Answer 3

La façon la plus simple de procéder avec STL (que je sache) consiste à supprimer l'entrée, à mettre à jour sa priorité, puis à la réinsérer. Cela est assez lent avec std :: priority_queue, cependant vous pouvez faire la même chose avec std :: set. Malheureusement, vous devez faire attention à ne pas changer la priorité d'un objet quand il est dans l'ensemble.

J'ai implémenté une classe mutable_priority_queue basée sur l'encollage de std :: multimap (pour le mappage de priorité à valeur) et de std :: map (pour le mappage de valeur à priorité) qui vous permet d'insérer / supprimer des éléments ainsi que de mettre à jour des éléments existants. valeurs en temps logarithmique. Vous pouvez obtenir le code et un exemple d'utilisation, ici

Answer 4

La structure de données appropriée est appelée "tas de Fibonacci". Mais vous devez l'implémenter vous-même. Insert / Updates are O (1) ExtractMin est O (logn)

Answer 5

J'ai mis en place une file d'attente prioritaire pouvant être mise à jour et hautement performante et la rendant disponible sur github .

Voici comment vous l'utiliseriez généralement:

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

Pour compléter la réponse de Jarekczek, si à la fois le set et le "tas pur avec des entrées inutiles" les approches ont la même complexité, la version stl :: set est généralement beaucoup plus lente que la version stl :: priority_queue en raison de son implémentation avec des arbres rouge-noir qui garantissent uniquement que leur profondeur soit inférieure à 2 * log_2 (n_elements) et nécessitent des mises à jour régulières, tandis que stl :: priority_queue est un segment binaire aussi pur et rapide que possible. C’est pourquoi il est généralement utilisé lors de l’implémentation de Dijkstra.

L'approche d'ensemble peut toutefois être plus rapide lorsque vous effectuez de nombreuses mises à jour sur quelques nœuds de base. C’est également là que l’utilisation de ma bibliothèque vous apporterait le plus d’améliorations.

Answer 6

Vous pouvez consulter replace_if avec un exemple ici .

Answer 7

Malheureusement, vous ne pouvez pas mettre à jour la valeur dans priority_queue. priority_queue n'offre pas une telle interface.

Je pense que vous feriez mieux d'utiliser set comme l'a dit Jarekczek ou d'utiliser cette solution ( en utilisant make_heap).