Hace ya unos días escribía un artículo sobre la Cola de Prioridad en PHP 7.4 que había implementado, y que está disponible en Github.
Por temas laborales he tenido que implementar el algoritmo de Dijkstra en PHP, y esto puede hacerse tanto con cola de prioridad como sin ella. La diferencia, en términos de coste de computación (Big O notation) era abismal, así que decidí usar la cola de prioridad al implementar Dijkstra. El problema era que mi cola de prioridad no tenía una función básica: «cambio de prioridad«.
Implementar ‘cambio de prioridad’ en la Cola de Prioridad en PHP
Después de analizar el código vi que era fácilmente implementable, testeable y usable en otros algoritmos, al estar debidamente encapsulada.
Para mi, además, resulta muy importante que el coste de computación fuera el menor posible. Idealmente tenía que ser el mismo que insertar y extirpar, que en esta cola es de O(log n). Cómo conseguir eso, teniendo en cuenta que usamos un ‘heap’ para mantener los elementos, representa claramente un gran reto.
La solución la basé en un elemento muy conocido de Java: el hashmap. A medida que la cola se va llenando (y vaciando) mantengo un apuntador a todos los elementos. Este apuntador es la clave de todo, porque consigo encontrar el elemento cuya prioridad hay que cambiar en O(1), con lo que las operaciones de up-heap o down-heap siguen manteniendo el coste O(log n). 🙂
El funcionamiento es muy simple: hay que obtener la posición del elemento cuya prioridad deseamos cambiar, cambiar su prioridad, y reposicionar mediante up-heap o down-heap.
Supongamos que hay que cambiar el elemento de prioridad 24 a prioridad 5. Como vemos en la imagen, tan sólo será necesario intercambiar su posición con el elemento 7 (su padre). Para ello necesitamos obtener la posición del elemento 24 (posición 5), comprobar que la prioridad del padre (posición 2) es menor, e intercambiar los elementos.
Hecho esto, la cola queda de la siguiente manera.
Et voilà! En este caso el cambio es muy sencillo, pero ilustra perfectamente la operativa. Y de verdad, el cambio de rendimiento en el algoritmo de Dijkstra es brutal. Simplemente brutal. 🙂
Échale un vistazo al repositorio de la cola de prioridad en PHP en Github.
Y si te gusta, ¡no dudes en comprarme un café!
