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

[Marco Antoniotti]

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 "librarize".

all the best


--
Marco Antoniotti

(*)  Full disclosure: a priority queue implementation by yours truly has been floating around for about 20 years now :)