heapq._siftdown / decrease-key support?
jabronson at gmail.com
Thu Jan 14 02:16:49 CET 2010
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.
Then I found Daniel Stutzbach's HeapDict, which looks like a whole
new package written just to support this operation (it also provides
some nice encapsulation to boot). So I switched. 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,
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.
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?
More information about the Python-list