I recently implemented A* search in Python using the heapq module and in my first pass, to accomplish the decrease-key operation I resorted to doing a linear scan of the list to find the position of the key in the heap, and then calling the private undocumented method heapq._siftdown at this position to enforce the heap property after updating the key's priority[1].
Then I found Daniel Stutzbach's HeapDict[2], which looks like a whole new package written just to support this operation (it also provides some nice encapsulation to boot). So I switched[3]. The cost of this improved implementation is slightly worse performance; I'm guessing this is because more code is being run in Python now rather than in C. Now I've just stumbled upon Mikael Lind's python-astar package[4], which implements A* using heapq without needing to use _siftdown; instead, if a better path to a neighbor is found, it marks the already- found node on the worse path as invalid, pushes a new node onto the heap with the improved priority, and at the end of each iteration, pops off any invalid nodes from the top of the heap[5]. Before I rewrite my code another time to see what kind of performance this results in, I figured I'd ask some interested parties first: Does heapq not provide decrease-key (and increase-key) because it expects you to work around it as Mikael has done, or for some other reason, or is it planned for the future? Thanks, Josh [1] http://bitbucket.org/jab/toys/src/7fe2965b275c/wordchain.py#cl-212 [2] http://github.com/DanielStutzbach/heapdict [3] http://bitbucket.org/jab/toys/src/2ae894c91d08/wordchain.py#cl-218 [4] http://github.com/elemel/python-astar [5] http://github.com/elemel/python-astar/blob/170c3d8c32c0c7ee24968c6d90fc6b6957461dec/src/astar.py#L112 -- http://mail.python.org/mailman/listinfo/python-list
