heapq._siftdown / decrease-key support?

[Terry Reedy]

On 1/14/2010 5:03 AM, Joshua Bronson wrote:
> 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.

If the values in the queue are associated with 0 to n-1, as can be used 
for graph node identifiers , the positions can also be kept in an list, 
again with 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.