STL Implémentation de reheapify

Question

Dans un algorithme de graphe, j'ai besoin de trouver le noeud avec la plus petite valeur.

Dans une étape de l'algorithme, la valeur de ce noeud ou de ses voisins peut être diminuée et certains de ses voisins peuvent être supprimés en fonction de leur valeur. En outre, je ne veux pas rechercher le graphique entier pour ce nœud à chaque fois (bien qu'il ne soit pas si grand (< 1000 nœuds)).

Par conséquent j'ai regardé la bibliothèque de STL et ai trouvé la structure de tas qui fait presque ce que je veux. Je peux insérer et supprimer des nœuds très rapidement, mais y a-t-il une méthode pour mettre à jour le tas rapidement quand je n'ai changé que la valeur d'un nœud sans avoir recours à tout le tas? Je pense que ce serait un énorme goulot d'étranglement dans le programme.

Answer 1

D'abord la partie conceptuelle: Si vous utilisez la méthode d'insertion de segment avec l'élément qui a diminué sa valeur comme point de départ pour l'insertion au lieu de commencer à la fin de la collection, tout fonctionne.

Je n'ai pas encore fait cela en C++, mais std :: push_heap a l'air bien dans ce but.