heapq._siftdown / decrease-key support?

[Joshua Bronson]

Thanks for the responses!

On Thu, Jan 14, 2010 at 12:23 AM, Daniel Stutzbach
<daniel at stutzbachenterprises.com> wrote:
> Your guess is correct.  Someday I'd like to rewrite HeapDict in C for speed, but I haven't been able to find the time (and no one has offered to pay me to make the time ;) ).

Daniel, did you realize you can accomplish logarithmic-time priority
change (albeit indirectly) with the built-in heapq module using this
mark-as-invalid trick? Are there other algorithms requiring decrease-
key besides A* and Dijkstra where this technique doesn't help?

On Thu, Jan 14, 2010 at 2:41 AM, Mikael Lind <elemel at elemel.se> wrote:
> If I recall correctly, avoiding the linear search did wonders for
> algorithm complexity.

It's still possible to perform the decrease-key operation without
having to do a linear search; heapdict does it in logarithmic time. If
my cursory benchmarks were accurate (which upon reconsideration I'm
not actually sure they are), I think the only explanation for it being
possibly slower is that it's running in pure Python.

I just switched back to using heapq but now with the mark-as-invalid
trick instead of the linear scan, and the performance I'm observing is
very close to heapdict's. Which is curious, because now that both
operations are running in logarithmic time, I'd expect the heapq
implementation to be much faster since it's written in C. Maybe I have
some confounding variables in how I'm running my tests.

By the way, I just realized that the obvious reason the heapq module
doesn't support priority change is that its functions are designed to
operate on external lists rather than providing an encapsulating data
structure like heapdict. With heapdict, logarithmic decrease_key is
possible because it's also storing the positions of the elements in an
underlying dictionary, so instead of a linear scan it does a constant-
time lookup. My guess is that the simplicity of having heapq operate
on external lists is preferable to supporting decrease-key directly,
so it isn't likely to change any time soon, especially since you can
accomplish the same thing with the mark-as-invalid technique.

Raymond, do you think this technique is worth documenting in the heapq
module? It'd be too bad if any future users incorrectly think that it
won't meet their needs the way I did.