[Python-Dev] Priority queue (binary heap) python code

[Magnus Lie Hetland]

Kevin O'Connor <kevin@koconnor.net>:
>
> I often find myself needing priority queues in python, and I've finally
> broken down and written a simple implementation.
[snip]

I see that heapq is now in the libraries -- great!

Just one thought: If I want to use this library in an algorithm such
as, say, Dijkstra's single-source shortest path algorithms, I would
need an additional operation, the deacrease-key operation (as far as I
can see, the heapreplace only works with index 0 -- wy is that?)

E.g.:

def heapdecrease(heap, index, item):
    """
    Replace an item at a given index with a smaller one.

    May be used to implement the standard priority queue method
    heap-decrease-key, useful, for instance, in several graph
    algorithms.
    """
    assert item <= heap[index]
    heap[index] = item
    _siftdown(heap, 0, index)

Something might perhaps be useful to include in the library... Or,
perhaps, the _siftup and _siftdown methods don't have to be private?

In addition, I guess one would have to implement a sequence class that
maintained a map from values to heap indices to be able to use
heapdecrease in any useful way (otherwise, how would you know which
index to use?). That, however, I guess is not something that would be
'at home' in the heapq module. (Perhaps that is argument enough to
avoid including heapdecrease as well? Oh, well...)

-- 
Magnus Lie Hetland                                  The Anygui Project
http://hetland.org                                  http://anygui.org