Эффективные способы найти значение, хранящееся в очереди приоритетов

Question

Я реализую поиск с равномерной стоимостью (UCS), используя очередь приоритета с std::vector для своего контейнера. UCS время от времени или, иногда, часто требует от меня уменьшения значения, уже находящегося в очереди с приоритетами.

std::priority_queue, по-видимому, не имеет такой возможности (1) искать ранее существующее значение, уже находящееся в очереди (2) настраивать значение в очереди

Я нашел в предыдущем посте, где кто-то предлагал создать такую ​​возможность самостоятельно, создав новый класс и написав линейную функцию поиска, но кажется неэффективным обходить всю очередь приоритетов для поиска значения.

Обратите внимание, что я написал и использую собственную структуру данных кучи min-max с использованием векторного контейнера, но он основан на том, что используется в STL.

Есть ли более эффективные способы сделать это? Один из способов, о котором я подумал, - это использовать std::map вместе с очередью приоритетов для отслеживания индексов. Это добавляет к сложности памяти, но этот метод, я думаю, только O (logn) сложность времени, где n - размер очереди.

Answer 1

Стандартная реализация кучи std :: priority_queue не предоставляет возможности изменить приоритет элемента, уже находящегося в очереди. Вы должны удалить его (стереть) и снова сделать pu sh (push_back + make_heap). Это в основном стоит O(n/2) для удаления, а затем O(n*log(n)) для восстановления кучи.

Вы можете взглянуть на boost :: heap для более специализированной реализации кучи, позволяющей изменить приоритет существующего элемента.