Introduction | Initialization | Closing | Adding | Deleting | Fetching | Parameters | Advanced | Obscure

A heap will always return the next best element (depending on your cost function) in the collection. Inserting elements will automatically place them in the correct sorted order according to their cost.

Since a heap can hold multiple elements with the same key, you can no
longer refer to a specific element by its key. LibDS uses a unique integer
index to identify each element in the heap. This is the only way you can
refer to a specific element in the heap. The index has to do with the absolute
position of the element in the heap. As operations are performed on the
heap, elements will be moved around and consequently their indices have
to be updated. If you are interested in keeping track of individual elements,
then you will somehow have to keep track of each element's index as it
changes. This HEAP implementation will let you pass it a pointer to a function
of the type `void (*HEAPCHGFUNC)(void*,int)` which will be called
every time that the index of the given data element has been changed. The
`int`
argument will hold the new index value of the element. Keeping track of
the index of an element is only necessary if you need to explicitly refer
to it, for example, if you want to delete a specific element. If you don't
need an element's index, then you don't need to pass a change function
pointer. This will spare the overhead of additional function calls.

As with the AVLTree implementation, a `HEAP`
needs a function to perform comparisons on the keys. The default is to
use C-strings of variable length, and `strcmp()` from the standard
C library. Given a comparison function, a heap can be made to keeps the
data in minimized or maximized order. See the section on initialization
on how to set this behavior.

As usual, items stored in the heap are void pointers to actual user data.

All data is stored in virtual memory.

Creates a new default heap. The value returned
is `NULL` if creation failed. The heap uses `strcmp()` as
comparison function and C-strings as keys. Data stored is minimized, that
is, the cheapest elements come first.

`HEAP heapNew(int (*cmpfun)(DSKEY,DSKEY),int
size,int
grow_by,int
mode)`

Creates a new heap. The heap has an original size
of *size*, and once that size is reached, the heap will automatically
grow by *grow_by* elements, to speed subsequent addition operations.
The parameter `mode` can be either `HEAP_MINIMIZE` or `HEAP_MAXIMIZE`.
This tells the heap whether to keep the data in ascending or descending
order.

`HEAP heapMakeIntKeys(int size,int grow_by,int
mode)`

Make a new heap that uses integers as keys. The parameters are the same
as `heapNew()`.

`HEAP heapMakeDoubleKeys(int size,int grow_by,int
mode)`

Make a new heap that uses doubles as keys. The parameters are the same
as `heapNew()`.

`HEAP heapMakeStringKeys(int size,int grow_by,int
mode)`

Make a new heap that uses strings as keys. The parameters are the same
as `heapNew()`.

`int heapSetChgFunc(HEAP heap, HEAPCHGFUNC fun)`

Sets the change function for this heap. For the definition of the `HEAPCHGFUNC`
type and the need for this function, see the

section Introduction. Returns 0 on success, -1
on failure.

Closes the heap, effectively releasing all memory used by it. User data remains untouched.

`void heapCloseWithFunction(HEAP heap,void
(*fun)(void*))`

Closes the heap, only this time call the function
*fun*
on each data element in the heap.

Adds a new element with key *key* to the heap. The function returns
the index into the heap array of the new element. On failure, -1 is returned.

Delete the element with index *idx* from the heap.

`void* heapFirst(HEAP heap)`

Delete the first element in the heap and returns its data. `NULL`
is returned on failure.

`void* heapFirst(HEAP heap)`

Delete and return the first element in the heap. Fails if the heap is empty.

`void* heapPeekFirst(HEAP heap)`

Returns the first element in the heap, but does not remove it. Fails if the heap is empty.

`void* heapElementAt(HEAP heap,int idx)`

Returns, but *does not* remove the element at in dex *idx*
in the heap. Fails if *idx* has a value smaller than zero, or larger
than the value returned by `heapSize()` (see Parameters).

Return the number of elements in the heap.

`int heapEmpty(HEAP heap)`

Returns true (value not equal to zero) if the heap has no more elements. Else, false (value equal to zero) is returned.

`void heapWalk(HEAP heap,HEAPWALKFUN fun)`

Visit all elements in the heap, and call *fun* on each one. The
elements are visited in binary tree fashion, using a pre-order walk.
`HEAPWALKFUN` is defined as `void (*)(int,const DSKEY,void*)`.
When called, the first argument will hold the depth of the element in the
binary tree view of the heap, the second will hold the element's key, and
the last holds the actual user data stored at this element.

Visit each element in the heap and call the print function. `HEAPPRINTFUNC
`has the signature `void (*)(int,const DSKEY,void*)` and when
called, the first argument will contain the depth of the item in the binary
tree representation, the second the item's key and the last one the item's
data. `heapPrintTree()` visits each node as they are seen in the
heap's binary tree representation, while `heapPrintArray()` visits
the nodes as they are seen in the heap's array representation.

`int heapCheck(HEAP heap)`

Performs some checks on the heap, to see if it conforms to the heap properties. Returns -1 if the checks fail, and 0 if all's OK.

True to this section's title, this is indeed obscure functionality.
As with all **Obscure** sections of LibDS's documentation this functionality
can be subjected to change without prior notice and should not be used
in a real implementation.

Sat Dec 15 18:12:34 EST 2001