[cdr-discuss] [cdr-announce] CDR 12 accepted

[Marco Antoniotti]

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 at cs.nyu.edu> wrote:

> 
> On Dec 10, 2012, at 11:49 , Marco Antoniotti <marcoxa at cs.nyu.edu> wrote:
> 
>> 
>> On Dec 9, 2012, at 21:31 , Nick Levine <ndl at ravenbrook.com> wrote:
>> 
>>> 1. Typo "devbelopers" for "developers".
>>> 
>>> 2. 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 at common-lisp.net
> http://lists.common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

--
Marco Antoniotti