Priority Queue in PHP

Today it's time to publish the code of a simple Priority Queue in PHP, but with an important update: the ability to change the priority to one element inside the queue.

This feature came across when I had to develop Dijkstra's Algorithm in PHP. The cost difference of Dijkstra's Algorithm in terms of Big O notation with a Priority Queue is simply amazing, so I couldn't do anything else; I had to implement it.  

The implementation of a method to change the priority of an element isn't difficult at all. It must be found, modified and reordered; that's pretty much it. But this, apparently very easy, must also be very efficient, and that's a bit more complicated. ;-)

In PHP, finding an element in a multi-level array is not very efficient (Cost O(n) if you use 'array_search'). This is, for me, unacceptable. The cost of finding an element should be O(1), and that's quite more complicated.

What I do to achieve this is to maintain an internal pointer called hashmap (like in Java). In this pointer I save a hash of the element, and a pointer to its current position. The difficult part is to have this pointer 'always' updated, and that's something I achieve by updating it while it is being up or down-heaped.

Using this technique, the change_priority method cost is, in the worst case, the cost of the up and down-heap operations: O(log n).

Let me know if you like this implementation of a Priority Queue in PHP.

And of course, if you want to use this Priority Queue in your PHP projects, feel free to download the code from github: https://github.com/oscarpascualbakker/priority-queue