Обновление очереди приоритетов STL при изменении ссылок на внутренние данные
Допустим, я пишу алгоритм Дейкстры, и у меня есть приоритетная очередь, которая держит самый короткий узел расстояния на вершине. Однако по мере прохождения графика я буду обновлять расстояние до этой вершины. Я разместил ссылки на все вершины в очереди приоритетов, которые содержатся в структуре данных. Теперь, когда я обновляю вершины в структуре данных, я хотел бы, чтобы данные в очереди приоритетов адаптировались к этим изменениям, поэтому ближайший узел всегда находится сверху. Однако, пройдя через мое приложение с отладчиком, я заметил, что приоритетная очередь не обновляется сама по себе. Как заставить его сделать это, не вставляя все вершины обратно в него?
1 ответ:
STL priority_queue предполагает, что для изменения структуры данных используются только методы push() и pop (). Он не отслеживает изменения в структуре данных.
После изменения внутренней части базового контейнера priority_queue необходимо вызвать функцию make_heap () для восстановления свойства кучи. STL priority_queue не предоставляет итераторы для базового контейнера. Вместо этого вам нужно вручную управлять deque или vector в качестве приоритетной очереди и вызывать make_heap(), push_heap () и pop_heap() по мере необходимости.