algorithm - orden - colas de prioridad java

¿Cómo implementar la operación de disminución de O(logn) para la cola de prioridad basada en min-heap?

Question

Estoy trabajando en una aplicación que demuestra el algoritmo del Djikstra , y para usarlo, necesito restaurar la propiedad del montón cuando se reduce el valor de mis elementos.

El problema con respecto a la complejidad es que cuando el algoritmo cambia el valor de un elemento, el índice de ese elemento en la estructura interna (montón en este caso) utilizado para la cola de prioridad es desconocido . Como tal, actualmente necesito hacer una búsqueda O (n), para recuperar el índice, antes de poder realizar una tecla de disminución real sobre él.

Además, no estoy exactamente seguro sobre el código real necesario para la operación. Estoy usando el D-Heap here para mi Priority Queue. El seudocódigo ayudaría, pero preferiría un ejemplo en Java sobre cómo se debe hacer esto.

Answer 1

Puede hacer lo siguiente: almacenar un hashmap dentro de su pila que mapea los valores de su pila a los índices de pila. Entonces deberías extender tu lógica heap habitual solo un poco:

on Swap(i, j):
map[value[i]] = j;
map[value[j]] = i;

on Insert(key, value):
map.Add(value, heapSize) in the beginning;

on ExtractMin:
map.Remove(extractedValue) in the end;

on UpdateKey(value, newKey):
index = map[value];
keys[index] = newKey;

BubbleUp(index) en caso de DecreaseKey , y BubbleDown/Heapify(index) en caso de IncreaseKey , para restaurar la propiedad min-heap.

Aquí está mi implementación de C #: http://pastebin.com/kkZn123m

Insertar y ExtraerMin llama al registro de Intercambio (N) veces, al restaurar la propiedad del montón. Y está agregando O (1) sobrecarga a Swap, por lo que ambas operaciones permanecen en O (log (n)). UpdateKey también es log (N): primero busca un índice en un hashmap para O (1), luego está restaurando la propiedad de montón para O (log (N)) como lo hace en Insert / ExtractMin.

Nota importante: el uso de valores para la búsqueda de índice requerirá que sean ÚNICOS. Si no está de acuerdo con esta condición, tendrá que agregar algún identificador único a sus pares clave-valor y mantener el mapeo entre este id único y el índice del montón en lugar del mapeo de índice de valor. Pero para Dijkstra no es necesario, ya que sus valores serán nodos de gráfico y no desea duplicar los nodos en su cola de prioridad.

Answer 2

Según esta pregunta SO, no es necesario tener un método de clave de disminución para implementar el algoritmo de Dijkstra.

Simplemente puede agregar un artículo a la cola de prioridad tantas veces como sea necesario y realizar un seguimiento de los nodos que ha visitado para eliminar los duplicados. La primera vez que visita un nodo saliéndolo de la cola, ha encontrado la ruta más corta hacia ese nodo y puede ignorar todas las apariciones futuras de la misma en la cola de prioridad.

Tener muchos nodos adicionales en la cola de prioridad no es un problema porque es una estructura O(log N) . (Debe hacer alrededor de 20 comparaciones para 1 millón de elementos y 30 de comparación para mil millones de elementos).

Editar: Siguiendo esta pregunta más adelante, estoy un poco decepcionado por mi respuesta: todas esas cosas tendrán que salir de la cola a menos que haga algunas canulaciones especiales más tarde. Como muchas cosas en la vida, se trata de cómo manejas tu memoria y los costos asociados con hacerlo. Pero el punto general sigue siendo: la tecla disminuir no es necesaria , incluso si pudiera ser deseable.

Answer 3

Si está utilizando c ++ stl make_heap () / pop_heap () / push_heap (), no hay forma de mantener un índice del ID del nodo para indexar en el vector de montón de subrayado, creo que debería implementar sus propias funciones de montón para lograr O ( logn) en la operación Increase-Key / Decrease-key.