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.