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

[Marco Antoniotti]

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