Dear all,
I believe that the document as it is is insufficient as a specification for a HEAP/PRIORITY-QUEUE data structure in CL.
I have several suggestions about how to proceed and change it.
If Ingvar agrees I can just go ahead and make the changes to the main LaTeX.
All the best
-- MA
On Dec 10, 2012, at 13:55 , Marco Antoniotti marcoxa@cs.nyu.edu wrote:
On Dec 10, 2012, at 11:49 , Marco Antoniotti marcoxa@cs.nyu.edu wrote:
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 "libraries".
Of course, I wrote the above just before double checking the last CLR edition. :) The operation in question is INCREASE-KEY (depends on whether you have a MAX or MIN Heap); DECREASE-KEY is instead mentioned in the chapter about SSSP problems. :)
Oh well.
-- Marco Antoniotti
cdr-discuss mailing list cdr-discuss@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss
-- Marco Antoniotti