Как выполнить эффективное обновление приоритета в STL priority_queue?

StackOverflow https://stackoverflow.com/questions/649640

  •  19-08-2019
  •  | 
  •  

Вопрос

У меня есть priority_queue некоторого объекта:

typedef priority_queue<Object> Queue;
Queue queue;

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

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

Я реализовал это таким образом, потому что в то время я немного спешил, и это было самое быстрое, что я мог сделать, чтобы быть уверенным, что все будет работать нормально.Однако должен быть способ получше, чем этот.На самом деле то, чего я хочу, - это способ либо:

  • извлеките экземпляр с измененным приоритетом и вставьте новый с новым значением приоритета
  • обновите экземпляр с измененным приоритетом, а затем обновите очередь, чтобы она была правильно отсортирована

Каков наилучший способ сделать это?

Это было полезно?

Решение

Я думаю, вам не повезло со стандартной очередью приоритетов, потому что вы не можете получить доступ к базовому deque / vector / list или чему-то еще.Вам нужно реализовать свой собственный - это не так уж сложно.

Другие советы

Я могу предложить 2 варианта решения проблемы, хотя ни один из них не выполняет реального обновления.

  1. Используйте priority_queue и нажимайте элемент каждый раз, когда вы хотите его обновить.Примите тот факт, что у вас будут бесполезные записи в очереди.При выводе верхнего значения проверьте, содержит ли оно актуальное значение.Если нет, проигнорируйте это и откройте следующее.

    Таким образом, вы откладываете удаление обновленного элемента до тех пор, пока он не дойдет до верха.Я заметил, что этот подход используется ведущими программистами, реализующими алгоритм Дейкстры.

  2. Использование set.Он также сортируется, чтобы вы могли извлечь наибольший элемент за логарифмическое время.Вы также можете удалить устаревший элемент, прежде чем вставить его снова.Таким образом, операция обновления по-прежнему невозможна, но удаление и повторная установка выполнимы.

Похоже, что сложность обоих подходов одинакова.

Самый простой способ сделать это с помощью STL (который я знаю) - удалить запись, обновить ее приоритет и затем снова вставить ее.Выполнение этого довольно медленно с помощью std::priority_queue, однако вы можете сделать то же самое с помощью std::set .К сожалению, вы должны быть осторожны, чтобы не изменить приоритет объекта, когда он находится в наборе.

Я реализовал класс mutable_priority_queue, основанный на склеивании std::multimap (для сопоставления приоритета со значением) и std::map (для сопоставления значения с приоритетом), который позволяет вставлять / удалять элементы, а также обновлять существующие значения в логарифмическое время.Вы можете получить код и пример того, как его использовать здесь

Соответствующая структура данных называется "Куча Фибоначчи".Но вам нужно реализовать это самостоятельно.Вставка / обновления - O (1) extractMin - O(logn)

Я внедрил высокопроизводительную обновляемую очередь приоритетов и сделал ее доступной на github.

Вот как вы обычно его используете :

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

Чтобы дополнить ответ Ярекчека, если действительно оба set и подходы "чистой кучи с бесполезными записями" имеют ту же сложность, что и stl::set версия обычно работает намного медленнее, чем stl::priority_queue версии из-за того, что она реализована с красно-черными деревьями, которые гарантируют, что их глубина будет меньше 2 * log_2 (n_elements) и требуют регулярных обновлений, в то время как stl::priority_queue это максимально чистая и быстрая двоичная куча, насколько это возможно.Вот почему он обычно используется при реализации Дейкстры.

Однако подход set может быть быстрее при выполнении большого количества обновлений на нескольких базовых узлах.Это также тот случай, когда использование моей библиотеки принесло бы вам наибольшие улучшения.

Возможно, вы захотите взглянуть на replace_if с примером здесь.

К сожалению, вы не можете обновить значение в priority_queue.priority_queue не предлагает такого интерфейса.

Я думаю, вам лучше использовать set как сказал Ярекчек , или использовать это решение(используя make_heap).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top