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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4