From: Marco Antoniotti <marcoxa@cs...> - 2000-09-07 13:59:09
as you may know, I have a PRIORITY QUEUE (HEAPS) package floating
around (it is in the AI Repository at CMU) that I wrote some time ago.
It basically implements the interface proposed in the CLR Book,
i.e. the Cormen Leiserson and Rivest (weighty) Intro to Algorithms. :)
After having recently used my own package in some serious work, I deem
it good enough for a release in the CLOCC.
However, I am not at all convinced about one of the operations that
you want to provide. The operation is "REDUCE-KEY" (a very mportant
operation in, say, Dijkstra shortest path algorithm).
Right now, I support this operation in a very transparent way for the
programmer, at the cost of keeping an hash table under the hood.
I.e. at each INSERT operation I stash the "item" as a key in the hash
table, with its "location" in the heap as value. When I need to do a
"REDUCE-KEY" (or "INCREASE-KEY") operation, I first get the "location"
from the hash table.
An alternative solution would be to make INSERT return two values: the
"regular" one (whatever that may be) and the "location" in the HEAP.
It then becomes the programmer's burden to keep track of this
information and to use it in a REDUCE-KEY operation.
What do you think?
Marco Antoniotti =============================================================
NYU Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://galt.mrl.nyu.edu/valis