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

[Tim Peters]

[Magnus Lie Hetland]
> 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

You'd need more than just that <wink>.

> (as far as I can see, the heapreplace only works with index 0 -- wy is
> that?)

heapreplace() is emphatically not a decrease-key operation.  It's equivalent
to a pop-min *followed by* a push, which combination is often called a
"hold" operation.  The value added may very well be larger than the value
popped, and, e.g., the example of an efficient N-Best queue in the test file
relies on this.  Hold is an extremely common operation in some kinds of
event simulations too, where it's also most common to push a value larger
than the one popped (e.g., when the queue is ordered by scheduled time, and
the item pushed is a follow-up event to the one getting popped).

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

That's the opposite of what heapreplace() usually sees.

>     heap[index] = item
>     _siftdown(heap, 0, index)
>
> Something might perhaps be useful to include in the library...

I really don't see how -- you generally have no way to know the correct
index short of O(N) search.  This representation of priority queue is
well-known to be sub-optimal for applications requiring frequent
decrease-key (Fibonacci heaps were desgined for it, though, and pairing
heaps are reported to run faster than Fibonacci heaps in practice despite
that one of the PH inventors eventually proved that decrease-key can destroy
PH's otherwise good worst-case behavior).

> Or, perhaps, the _siftup and _siftdown methods don't have to be
> private?

You really have to know what you're doing to use them correctly, and it's
dubious that _siftup calls _siftdown now (it's most convenient *given* all
the uses made of them right now, but, e.g., if a "delete at arbitrary index"
function were to be added, _siftdown and _siftup could stand to be
refactored -- exposing them would inhibit future improvements).

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

Bingo.  All the internal heap manipulations would have to know about this
mapping too, in order to keep the indices up to date as it moved items up
and down in the queue.  If want you want is frequent decrease-key, you don't
want this implementation of priority queues at all.