[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:1.8.1.1) Gecko/20061205 Iceweasel/2.0.0.1 (Debian-2.0.0.1+dfsg-1) |
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/