On Dec 9, 2012, at 21:31 , Nick Levine ndl@ravenbrook.com wrote:
Typo "devbelopers" for "developers".
Maybe I'm just dim, but I really don't understand what this is
about. The functional interface looks like that of a queue (or a stack, depending on whether insert and remove work on the same end as each other or not). Can you explain? give a couple of examples?
A "Heap" is also known as a "Priority Queue". So the interface must be similar.
I have nothing against this (*), although the spec leaves out a few corner cases. E.g., what happens when the keys are equal, but the values/content associated are not?
Apart from that, I do not understand the use of DECLARE-HEAP and I believe that there should be no provisions to define a package for these sort of data structures. Or better: I believe a discussion about how to structure packages and libraries should be started. But this is an old pet peeve of mine.
Finally, and maybe much more critical, a key operation on Heaps is REDUCE-KEY (to use the now standard CLR terminology). Without it you cannot implement Dijkstra SSSP algorithm. Problem is, this operation assumes the presence of "fingers" (read: "pointers") in the heap, not an easy thing to "librarize".
all the best
-- Marco Antoniotti
(*) Full disclosure: a priority queue implementation by yours truly has been floating around for about 20 years now :)