[Python-Dev] Re: heapq (original) (raw)

David Eppstein eppstein@ics.uci.edu
Sat, 19 Apr 2003 16:06:19 -0700

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