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

Question

у меня есть 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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

Я реализовал высокопроизводительную обновляемую очередь с приоритетами и сделал ее доступной на 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 является настолько чистой и быстрой двоичной кучей, насколько это возможно. Вот почему он обычно используется при реализации Dijkstra.

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

Answer 6

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

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

Answer 7

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