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



In a nutshell, a heap is a data structure that keeps its data ordered according to their keys. The difference between a heap and a binary tree is in the fact that the heap supports multiple elements with the same key. Technically, a binary tree can be made to do this as well, in which case it will be able to do exactly the same as a heap. I guess this means that you can use a binary tree that supports duplicate keys to do the work of a heap. But anyway, LibDS has its own heap implementation, and it is a true heap (i.e. it's not a binary tree). LibDS refers to a heap as HEAP.

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.


HEAP heapMake(void)

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.


void heapClose(HEAP heap)

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.


int heapAdd(HEAP q,const DSKEY key,void *data)
int heapInsert(HEAP q,const DSKEY key,void *data)

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.


void* heapDelete(HEAP heap,int idx)

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.


As usual, whenever a void* is returned, it contains user data, or NULL if something went wrong. Therefore, storing NULL as a value will not be distinguished from an error.

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).


int heapSize(HEAP heap)

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.

Advanced funtionality

Visiting the elements of the HEAP

You can visit all elements in the heap and call a function to be performed on each data item found in each element.

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.

Obscure functionality

void heapPrintTree(HEAP heap,HEAPPRINTFUNC pfun)
void heapPrintArray(HEAP heap,HEAPPRINTFUNC pfun)

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