Actualizar cola de prioridad STL al modificar referencias a datos internos

Question

Digamos que estoy escribiendo Dijkstra's Algorithm, y tengo una cola de prioridad que mantiene el nodo de distancia más corta en la parte superior. Sin embargo, mientras recorro el gráfico, actualizaré la distancia a ese vértice. He colocado referencias a todos los vértices en la cola de prioridad que están contenidos en la estructura de datos. Ahora, al actualizar los vértices en la estructura de datos, me gustaría que los datos en la cola de prioridad se adapten a esos cambios, de modo que el nodo más cercano siempre esté en la parte superior. Sin embargo, después de recorrer mi aplicación con el depurador, noté que la cola de prioridad no se actualiza. ¿Cómo lo hago para hacer esto, sin volver a insertar todos los vértices?

Answer 1

STL priority_queue supone que solo utiliza los métodos push() y pop() para modificar la estructura de datos. No realiza un seguimiento de los cambios en la estructura de datos.

Después de modificar el interior del contenedor subyacente de priority_queue, necesita llamar a make_heap() en el contenedor para restaurar la propiedad del montón. STL priority_queue no proporciona iteradores en el contenedor subyacente. En su lugar, debe administrar manualmente un deque o un vector como cola de prioridad y llamar a make_heap(), push_heap() y pop_heap() según sea necesario.