cgul_heap_primitives.h File Reference

primitive heap operations More...

#include "cgul_common.h"
#include "cgul_exception.h"

Include dependency graph for cgul_heap_primitives.h:

This graph shows which files directly or indirectly include this file:

Functions
CGUL_EXPORT void	cgul_heap_primitives__heapify (cgul_exception_t *cex, void **v, size_t v_count, cgul_heap_primitives__compare_t cf)
CGUL_EXPORT void	cgul_heap_primitives__shift_down (cgul_exception_t *cex, void **v, size_t v_count, size_t index, int use_floyds_method, cgul_heap_primitives__compare_t cf)
CGUL_EXPORT void	cgul_heap_primitives__shift_up (cgul_exception_t *cex, void **v, size_t v_count, size_t index, cgul_heap_primitives__compare_t cf)

Variables
CGUL_BEGIN_C typedef int(*	cgul_heap_primitives__compare_t )(const void *e1, const void *e2)

Detailed Description

Primitive heap operations that can be performed on a Binary Heap represented as an array.

Author

Paul Serice

Function Documentation

cgul_heap_primitives__heapify()

CGUL_EXPORT void cgul_heap_primitives__heapify	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		cgul_heap_primitives__compare_t	cf
	)

This function converts the unordered array v into a heap. This is done using the bottom-up algorithm which is O(n).

Parameters

[in]	cex	c-style exception
[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	cf	comparison function

Referenced by cgul_heap_primitives_cxx::heapify().

cgul_heap_primitives__shift_down()

CGUL_EXPORT void cgul_heap_primitives__shift_down	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		size_t	index,
		int	use_floyds_method,
		cgul_heap_primitives__compare_t	cf
	)

Shift the element at v[index] down until it is greater than or equal to all of its descendants as determined by the comparison function cf. (This code is for a max-heap.)

If floyd is true, Floyd's Method is used as an optimization to reduce the number of callbacks required to the comparison function. It works by initially assuming the value being shifted down is smaller than both children causing the larger child to be shifted up at each level until a leaf node is reached. Then, cgul_heap_primitives__shift_up() is called to find the correct location for the value. This is an optimization when forced to replace the root value with a value from the back of the array which is probably smaller than all the values along the path described.

Note

Do not use Floyd's Method until after the heap has been fully constructed because cgul_heap_primitives__shift_up() assumes the heap is fully constructed.

Parameters

[in]	cex	c-style exception
[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	index	index of element to be shifted down
[in]	use_floyds_method	use Floyd's Method
[in]	cf	comparison function

Referenced by cgul_heap_primitives_cxx::shift_down().

cgul_heap_primitives__shift_up()

CGUL_EXPORT void cgul_heap_primitives__shift_up	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		size_t	index,
		cgul_heap_primitives__compare_t	cf
	)

Shift the element at v[index] up until it is the root element or until it is greater than or equal to all of its descendants but less than its parent as determined by the comparison function cf. (This code is for a max-heap.)

Parameters

[in]	cex	c-style exception
[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	index	index of element to be shifted down
[in]	cf	comparison function

Referenced by cgul_heap_primitives_cxx::shift_up().

Variable Documentation

cgul_heap_primitives__compare_t

CGUL_BEGIN_C typedef int(* cgul_heap_primitives__compare_t) (const void *e1, const void *e2)

This typedef is the interface the client must define in order for the cgul_heap_primitives functions to maintain heap order. When defining the comparison function, it should compare e1 to e2 and return less than zero, zero, or greater than zero if e1 is less than, equal to, or greater than e2.

Parameters

[in]	e1	first element
[in]	e2	second element

Returns

result of comparison