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

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

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

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

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

Ответы

Ответ 1

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

Вы можете посмотреть replace_if с примером здесь.

Ответ 6

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

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

Ответ 7

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

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

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