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

Magnus Lie Hetland magnus@hetland.org
Sun, 11 Aug 2002 15:44:46 +0200

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.

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?)


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
    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