[patch #5667] Add heap (priority queue) implementation to libpspp

[Ben Pfaff]

Follow-up Comment #2, patch #5667 (project pspp):

It seems that I forgot to write any documentation.  How thoughtless of me. 
Here's a comment that I've added to my working tree now:


/* Embedded priority queue, implemented as a heap.

   Operations have the following cost, where N is the number of
   nodes already in the heap:

        - Insert: O(lg N).

        - Find minimum: O(1).

        - Delete any node in the heap: O(lg N).

        - Change value of an node: O(lg N) in general; O(1) in
          the typically common case where the node does not
          change its position relative to other nodes.

        - Search for a node: O(N).  (Not implemented; if you need
          such a routine, use a different data structure or
          maintain a separate index.)

   A heap data structure is structured as a packed array.  If an
   array is a natural data structure for your application, then
   use the push_heap, pop_heap, make_heap, sort_heap, and is_heap
   functions declared in libpspp/array.h.  Otherwise, if your
   data structure is more dynamic, this implementation may be
   easier to use.

   An embedded heap is represented as `struct heap'.  Each node
   in the heap, presumably a structure type, must include a
   `struct heap_node' member.

   Here's an example of a structure type that includes a `struct
   heap_node':

     struct foo
       {
         struct heap_node node;   // Heap node member.
         int x;                   // Another member.
       };

   Here's an example of how to find the minimum value in such a
   heap and delete it:

     struct heap *h = ...;
     if (!heap_is_empty (h)) 
       {
         struct foo *foo = heap_data (heap_minimum (h), struct foo, node);
         printf ("Minimum is %d.\n", foo->x);
         heap_delete (h, &foo->node);
       }
     else
       printf ("Heap is empty.\n");
*/


>I was confused by the function is_heap. What does UNUSED mean on
>the return value? If the return value is never used, then why 
>not return void? Or does it mean the function itself is never 
>used (in which case why have it?) Similarly is_k_composition.

It means that the function may not be used.  It suppresses a warning when
compiled with -DNDEBUG.  Would you like it better if I put this stuff in
#ifdef NDEBUG...#endif?

>It seems that argument 1 of less and lesser_node could be const.

OK, done.

> My guess is, that the most common use would want the aux
>arguments of heap_create and heap_compare_func to be const. 

OK, done.  (My current usage case doesn't use aux at all.)

>If struct heap_node is opaque, then why have it in the .h file ?

I hope that my doc comment above cleared this up.

>How about a version of heap_create, which uses a pool, the same 
>as we have for hash? 

OK, done.

>A version, where the nodes inserted are const?

I think that's less useful for a heap than for (say) a hash table, because
one of the reasons to use a heap instead of, say, a statically sorted table
is that it gracefully handles nodes whose priority changes.

If this documentation explains what's going on well enough, then I'll check
it in.



    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?5667>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/