c++ - example - priority queue java

¿Cómo hacer una actualización de prioridad eficiente en STL priority_queue?

Question

Tengo una priority_queue de algún objeto:

typedef priority_queue<Object> Queue;
Queue queue;

De vez en cuando, la prioridad de uno de los objetos puede cambiar: necesito poder actualizar la prioridad de ese objeto en la cola de una manera eficiente. Actualmente estoy usando este método que funciona pero parece ineficiente:

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

Lo implementé de esta manera porque tenía mucha prisa en ese momento y fue lo más rápido que pude hacer para estar seguro de que funcionaría bien. Sin embargo, tiene que haber una mejor manera que esto. Realmente lo que quiero es una forma de:

• extraer la instancia con la prioridad modificada e insertar una nueva con el nuevo valor de prioridad
• actualice la instancia con la prioridad modificada y luego actualice la cola para que esté correctamente ordenada

¿Cuál es la mejor manera de hacer esto?

Answer 1

Creo que no tienes suerte con la cola de prioridad estándar porque no puedes acceder al deque / vector / list o lo que sea. Necesitas implementar la tuya, no es tan difícil.

Answer 2

Es posible que desee echar un vistazo a replace_if con un ejemplo aquí .

Answer 3

La forma más sencilla de hacerlo con STL (que yo sepa) es eliminar la entrada, actualizar su prioridad y luego reinsertarla. Hacer esto es bastante lento usando std :: priority_queue, sin embargo, puede hacer lo mismo con std :: set. Lamentablemente, debe tener cuidado de no cambiar la prioridad de un objeto cuando está en el conjunto.

He implementado una clase mutable_priority_queue basada en el pegado de std :: multimap (para asignación de prioridad a valor) y std :: map (para mapeo de valor a prioridad) que le permite insertar / eliminar elementos, así como actualizar los valores existentes en logarítmico hora. Puede obtener el código y un ejemplo de cómo usarlo aquí

Answer 4

La estructura de datos apropiada se llama "Fibonacci Heap". Pero debes implementarlo tú mismo. Insertar / Actualizaciones son O (1) ExtractMin es O (logn)

Answer 5

Puedo sugerir 2 opciones para resolver el problema, aunque ninguno realiza una actualización real.

1. Utilice los elementos priority_queue y push cada vez que desee actualizarlo. Acepte el hecho de que tendrá entradas inútiles en la cola. Cuando aparezca el valor superior, verifique si contiene el valor actualizado. Si no, ignóralo y presiona el siguiente.

   De esta manera, retrasa la eliminación del elemento actualizado hasta que llegue a la cima. Me di cuenta de que este enfoque está siendo utilizado por los mejores programadores al realizar el algoritmo de Dijkstra.

2. Usar set . También está ordenado para que pueda extraer el elemento más grande en tiempo logarítmico. También puede eliminar el elemento obsoleto antes de volver a insertarlo. Por lo tanto, todavía no es posible realizar ninguna operación de actualización, pero la eliminación y la reinserción son factibles.

Parece que la complejidad de ambos enfoques es la misma.

Answer 6

Desafortunadamente no puedes actualizar el valor en priority_queue. priority_queue no ofrece dicha interfaz.

Creo que es mejor usar set como dijo Jarekczek o usar esta solución (usando make_heap).