Как сделать эффективное обновление приоритета в 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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

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

Answer 6

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

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