heapq._siftdown / decrease-key support?

Joshua Bronson 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[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



More information about the Python-list mailing list