patchPSPP - Patches: patch #5667, Add heap (priority queue)...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

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

Submitted by:  Ben Pfaff <blp>
Submitted on:  Tue 09 Jan 2007 05:30:46 AM UTC  
 
Category:  None Item Group:  None
Status:  Done Assigned to:  Ben Pfaff <blp>
Open/Closed:  Closed

Wed 10 Jan 2007 02:50:42 PM UTC, comment #4: 

Thanks!

I checked this in.

Ben Pfaff <blp>
Project AdministratorIn charge of this item.
Wed 10 Jan 2007 06:33:59 AM UTC, comment #3: 

Seems fine to me.

John Darrington <jmd>
Project Administrator
Wed 10 Jan 2007 03:52:20 AM UTC, comment #2: 

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.

Ben Pfaff <blp>
Project AdministratorIn charge of this item.
Tue 09 Jan 2007 09:50:19 PM UTC, comment #1: 

I can't see any major issues.

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 seems that argument 1 of less and lesser_node could be const.

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

Perhaps the comment in heap.h needs to be clearer:
/* A node in a heap.  Opaque. */
struct heap_node
  {
    size_t idx;
  };
If struct heap_node is opaque, then why have it in the .h file ?  
I think you mean that heap nodes must have a idx member, but all other elements are indeterminate.

Other issues, which may or may not be relevent, depending on how you're intending to use this:

  1. How about a version of heap_create, which uses a pool, the same as we have for hash?
  1. A version, where the nodes inserted are const?
John Darrington <jmd>
Project Administrator
Tue 09 Jan 2007 05:30:46 AM UTC, original submission:  

The attached patch adds a priority queue (implemented as a heap) implementation to src/libpspp.  It's a small part of a much larger patch I'm planning to present later.

Comments?

Ben Pfaff <blp>
Project AdministratorIn charge of this item.

 

Attached Files
file #11705:  heap.patch added by blp (30KiB - text/x-patch - patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jmd (Posted a comment)
  • -email is unavailable- added by blp (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2007-01-10 blp StatusReady For Test/Review => Done
        Open/ClosedOpen => Closed
    2007-01-09 jmd Assigned tojmd => blp
    2007-01-09 blp Attached File- => Added heap.patch, #11705

    Back to the top


    Powered by Savane 3.5