[Python-Dev] Re: heapq

[David Eppstein]

In article <20030419224110.GB2460@barsoom.org>,
 Agthorr <agthorr@barsoom.org> wrote:

> The algorithms used are more or less identical, I'm primarily
> concerned with the differences in interface.

It seems relevant to point out my own experiment with an interface to 
priority queue data structures, 
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228

The algorithm itself is an uninteresting binary heap with lazy 
deletion, I am interested here more in the API.  My feeling is that 
"queue" is the wrong metaphor to use for a heap, since it maintains not 
just a sequence of objects (as in a queue) but a more general mapping 
of objects to priorities.  In many algorithms (e.g. Dijkstra), you want 
to be able to change these priorities, not just add and remove items 
the way you would in a queue.

So, anyway, I called it a "priority dictionary" and gave it a 
dictionary-like API:
    pd[item] = priority 
adds a new item to the heap with the given priority, or updates the 
priority of an existing item, no need for a separate decrease_key method 
as you suggest.  There is an additional method for finding the 
highest-priority item since that's not a normal dictionary operation.

I also implemented an iterator method that repeatedly finds and removes 
the highest priority item, so that "for item in priorityDictionary" 
loops through the items in priority order.  Maybe it would have been 
better to give this method a different name, though, since it's quite 
different from the usual not-very-useful dictionary iterator.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science