[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Ben Pfaff
Subject: [patch #5667] Add heap (priority queue) implementation to libpspp
Date: Wed, 10 Jan 2007 03:52:21 +0000
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv: Gecko/20061205 Iceweasel/ (Debian-

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

     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);
       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:


  Message sent via/by Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]