Heaps

This module provides a Heap mechanism. More...

Typedefs
typedef struct dheap	dheap_t
	Opaque type for a heap.
Enumerations
enum	dheap_result_t { DHEAP_SUCCESS = 0, DHEAP_FULL = 1, DHEAP_EMPTY = 2 }
	Return values for heap insertion and extraction functions. More...
Functions
dheap_t *	dheap_new (size_t size, dcmp_cb_t cmp)
	Constructor for a heap.
void	dheap_free (dheap_t *h, dfree_cb_t fc)
	Destructor for a heap.
dheap_result_t	dheap_insert (dheap_t *h, void *val)
	Insert procedure.
dheap_result_t	dheap_extract (dheap_t *h, void **val)
	Extract the greatest element, than run heapify_down over the values array.
void	dheap_heapify_up (void *values[], size_t used, dcmp_cb_t cmp)
	Correct the heapify structure from below.
void	dheap_heapify_down (void *values[], size_t used, dcmp_cb_t cmp)
	Move the last element on top, and correct the heapify structure from above.

---

Detailed Description

This module provides a Heap mechanism.

This kind of mechanism is tipically used for priority queues implementation, because allows to select in a very efficient way the greatest or the least element of a set.

---

Enumeration Type Documentation

enum dheap_result_t

Return values for heap insertion and extraction functions.

See also:

dheap_insert for data insertion;

dheap_extract for data insertion.

Enumerator:

DHEAP_SUCCESS	Operation successful;.
DHEAP_FULL	Full heap;.
DHEAP_EMPTY	Empty heap.

---

Function Documentation

dheap_result_t dheap_extract	(	dheap_t *	h,
		void **	val
	)

Extract the greatest element, than run heapify_down over the values array.

Parameters:

[in]	h	The heap;
[in]	val	The position where the value will be positioned.

Return values:

dheap_result_t::DHEAP_SUCCESS	on success;
dheap_result_t::DHEAP_EMPTY	if the array is empty.

void dheap_free	(	dheap_t *	h,
		dfree_cb_t	fc
	)

Destructor for a heap.

Parameters:

[in]	h	The heap to be destructed;
[in]	fc	The callback used to deallocate any internal object (you may provide NULL if the object does not need to be deallocated).

void dheap_heapify_down	(	void *	values[],
		size_t	used,
		dcmp_cb_t	cmp
	)

Move the last element on top, and correct the heapify structure from above.

This absumes that the structure is already correctly stored. The first value must be saved before this operation, since it gets lost.

This operation is logically equivalent to removing the greatest value and rebuilding the heap structure. After running it you shuld decrement of 1 the size of the used variable.

Note:

This function is somehow to be considered private: it's used by the dheap_insert function in order to keep the array correctly heapified. It has been exported so that you can use it on a generic vector.

Parameters:

[in]	values	The values array;
[in]	used	The total number of elements (last used slot included);
[in]	cmp	The (mandatory) callback used to compare two objects, must behave like the strcmp(3) function.

See also:

dcmp_cb_t.

void dheap_heapify_up	(	void *	values[],
		size_t	used,
		dcmp_cb_t	cmp
	)

Correct the heapify structure from below.

This absumes that only the last element is not correctly stored. Typically this happens when a new element has been added on the last slot.

Note:

This function is somehow to be considered private: it's used internally by the dheap_insert() function in order to keep the array correctly heapified. It has been exported so that you can use it on a generic vector.

Parameters:

[in]	values	The values array;
[in]	used	The total number of elements (last used slot included).
[in]	cmp	The (mandatory) callback used to compare two objects, must behave like the strcmp(3) function.

See also:

dcmp_cb_t.

dheap_result_t dheap_insert	(	dheap_t *	h,
		void *	val
	)

Insert procedure.

Insert one element in the first position of the heap_t structure, than run heapify_up over the values array.

Parameters:

[in]	h	The heap;
[in]	val	The value to be inserted.

Return values:

dheap_result_t::DHEAP_SUCCESS	on success;
dheap_result_t::DHEAP_FULL	if the array is full.

dheap_t* dheap_new	(	size_t	size,
		dcmp_cb_t	cmp
	)

Constructor for a heap.

The implementation requires a fixed size for the heap.

Parameters:

[in]	size	The size of the heap to be allocated;
[in]	cmp	The callback used to compare two objects, must behave like the strcmp(3) function (or NULL if the objects should be directly compared by pointer subtraction).

Returns:

The newly allocated heap.