montones - La forma más sencilla de usar la cola de prioridad mínima con la actualización de la clave en C++

ejemplo de colas (3)

Aunque mi respuesta no responderá a la pregunta original, creo que podría ser útil para las personas que llegan a esta pregunta cuando intentan implementar el algoritmo de Dijkstra en C ++ / Java (como yo), algo que fue comentado por el OP,

priority_queue en C ++ (o PriorityQueue en Java) no proporcionan una operación de decrease-key , como se dijo anteriormente. Un buen truco para usar esas clases al implementar Dijkstra es usar "eliminación diferida". El ciclo principal del algoritmo Dijkstra extrae el siguiente nodo para ser procesado desde la cola de prioridad, y analiza todos sus nodos adyacentes, eventualmente cambiando el costo de la ruta mínima para un nodo en la cola de prioridad. Este es el punto donde normalmente se necesita decrease-key para actualizar el valor de ese nodo.

El truco no es cambiarlo en absoluto. En su lugar, se agrega una "nueva copia" para ese nodo (con su nuevo costo mejor) en la cola de prioridad. Al tener un costo menor, esa nueva copia del nodo se extraerá antes de la copia original en la cola, por lo que se procesará antes.

El problema con esta "eliminación diferida" es que la segunda copia del nodo, con el mayor costo negativo, se extraerá finalmente de la cola de prioridad. Pero eso siempre ocurrirá después de que se haya procesado la segunda copia añadida, con un mejor costo. Entonces, lo primero que debe hacer el bucle principal de Dijkstra al extraer el siguiente nodo de la cola de prioridad es verificar si el nodo ha sido visitado previamente (y ya conocemos la ruta más corta). Es en ese momento preciso cuando realizaremos la "eliminación diferida" y el elemento simplemente debe ignorarse.

Esta solución tendrá un costo tanto en la memoria como en el tiempo, ya que la cola de prioridad almacena los "elementos muertos" que no hemos eliminado. Pero el costo real será bastante pequeño, y la programación de esta solución es, en mi humilde opinión, más fácil que cualquier otra alternativa que intente simular la operación de decrease-key .

A veces, durante los concursos de programación, etc., necesitamos una implementación de trabajo simple de cola de prioridad mínima con tecla de disminución para implementar el algoritmo de Dijkstra, etc. A menudo uso set <pair <key_value, ID>> y una matriz (mapping ID -> key_value ) juntos para lograr eso.

Agregar un elemento al conjunto toma el tiempo O (log (N)). Para construir una cola de prioridad a partir de N elementos, simplemente los agregamos uno por uno en el conjunto. Esto toma el tiempo O (N log (N)) en total.
El elemento con min key_value es simplemente el primer elemento del conjunto. Sondear el elemento más pequeño toma O (1) vez. Quitarlo toma el tiempo O (log (N)).
Para comprobar si algún ID = k está en el conjunto, primero buscamos su key_value = v_k en el conjunto y luego buscamos el elemento (v_k, k) en el conjunto. Esto toma el tiempo O (log (N)).
Para cambiar el key_value de algunos ID = k de v_k a v_k '', primero buscamos su key_value = v_k en el array, y luego buscamos el elemento (v_k, k) en el conjunto. Luego eliminamos ese elemento del conjunto y luego insertamos el elemento (v_k '', k) en el conjunto. Luego actualizamos la matriz también. Esto toma el tiempo O (log (N)).

Aunque el enfoque anterior funciona, la mayoría de los libros de texto generalmente recomiendan usar pilas binarias para implementar colas de prioridad, ya que el tiempo de construcción de las pilas binarias es solo O (N). Escuché que hay una estructura de datos de cola de prioridad incorporada en STL de C ++ que usa montones binarios. Sin embargo, no estoy seguro de cómo actualizar el key_value para esa estructura de datos.

¿Cuál es la forma más fácil y más eficiente de utilizar la cola de prioridad mínima con la actualización de la clave en C ++?

No creo que la clase std::priority_queue permita una implementación eficiente de decrease-key operaciones de estilo de decrease-key .

Lancé mi propia estructura de datos basada en el montón binario que es compatible con esto, básicamente a lo largo de líneas muy similares a lo que ha descrito para la cola de prioridad basada en std::set que tiene:

Mantenga un montón binario, ordenado por value que almacena elementos del pair<value, ID> y una matriz que mapea ID -> heap_index . Dentro de las rutinas de montón heapify_up, heapify_down etc., es necesario garantizar que la matriz de mapeo se mantenga sincronizada con la posición de montón actual de los elementos. Esto agrega un poco más de O(1) sobrecarga.
La conversión de una matriz a una pila se puede hacer en O(N) acuerdo con el algoritmo estándar descrito here .
Leer en el elemento raíz es O(1) .
Verificando si una ID está actualmente en el montón solo requiere una O(1) búsqueda en la matriz de mapeo. Esto también permite que O(1) busque en el elemento correspondiente a cualquier ID .
Decrease-key requiere una búsqueda O(1) en la matriz de asignación seguida de una actualización O(log(N)) en el heapify_up, heapify_down dinámico a través de heapify_up, heapify_down .
Al presionar un nuevo elemento en el montón, se muestra O(log(N)) como aparece un elemento que sale del montón.

Tan asintóticamente, el tiempo de ejecución se mejora para algunas de las operaciones en comparación con la estructura de datos basada en std::set . Otra mejora importante es que los montones binarios se pueden implementar en una matriz, mientras que los árboles binarios son contenedores basados en nodos. La localidad de datos extra del montón binario generalmente se traduce en tiempo de ejecución mejorado.

Algunos problemas con esta implementación son:

Solo permite números enteros de ID .
Supone una distribución ajustada de los ID de artículo, comenzando en cero (de lo contrario, ¡la complejidad del espacio de la matriz de mapeo explota!).

Podría superar estos problemas si mantiene una tabla hash de asignación, en lugar de una matriz de asignación, pero con un poco más de tiempo de ejecución. Para mi uso, los ID enteros siempre han sido suficientes.

Espero que esto ayude.

Bueno, como ya dijo Darren, std::priority_queue no tiene medios para disminuir la prioridad de un elemento y tampoco la eliminación de un elemento que no sea el mínimo actual. Pero la predeterminada std::priority_queue no es más que un simple adaptador de contenedor alrededor de un std::vector que usa las funciones std heap de <algorithm> ( std::push_heap , std::pop_heap y std::make_heap ). Entonces, para Dijkstra (donde se necesita una actualización de prioridad) generalmente solo hago esto y uso un std::vector simple.

Un impulso es simplemente la operación O (log N)

vec.push_back(item); std::push_heap(vec.begin(), vec.end());

Por supuesto, para construir una cola de nuevo desde N elementos, no los empujamos a todos usando esta operación O (log N) (haciendo todo O (Nlog N)) sino que simplemente los puse todos en el vector seguido de un simple O (NORTE)

std::make_heap(vec.begin(), vec.end());

El elemento min es un simple O (1)

vec.front();

Un pop es la secuencia simple O (log N)

std::pop_heap(vec.begin(), vec.end()); vec.pop_back();

Hasta ahora, esto es exactamente lo que std::priority_queue generalmente hace bajo el capó. Ahora, para cambiar la prioridad de un elemento, solo tenemos que cambiarlo (sin embargo, se puede incorporar en el tipo del elemento) y hacer que la secuencia vuelva a ser un montón válido

std::make_heap(vec.begin(), vec.end());

Sé que se trata de una operación O (N), pero, por otro lado, elimina la necesidad de mantener un registro de la posición de un elemento en el montón con una estructura de datos adicional o (incluso peor) un aumento del tipo de elementos. Y la penalización de rendimiento sobre una actualización de prioridad logarítmica en la práctica no es tan significativa, considerando la facilidad de uso, el uso de memoria lineal y compacta de std::vector (que también afecta el tiempo de ejecución) y el hecho de que a menudo trabajo con gráficos que tener muy pocos bordes (lineales en el conteo de vértices) de todos modos.

Puede que en ningún caso sea la manera más rápida, pero ciertamente la más fácil.

EDITAR: Ah, y dado que la biblioteca estándar usa max-montones, necesita usar un equivalente a > para comparar las prioridades (independientemente de cómo las obtenga de los elementos), en lugar del operador predeterminado < .