cgul_heap_primitives_cxx Class Reference

C++ bindings for cgul_heap_primitives More...

#include <cgul_heap_primitives_cxx.h>

Collaboration diagram for cgul_heap_primitives_cxx:

Public Types
typedef cgul_heap_primitives__compare_t	compare_t

Static Public Member Functions
static void	heapify (void **v, size_t v_count, compare_t cf)
static void	shift_down (void **v, size_t v_count, size_t index, int use_floyds_method, compare_t cf)
static void	shift_up (void **v, size_t v_count, size_t index, compare_t cf)

Detailed Description

This class provides the C++ bindings for C cgul_heap_primitives functions. The main purpose of this class is to convert the C-style function calls and exception handling in cgul_heap_primitives into C++-style function calls and exception handling.

Member Typedef Documentation

compare_t

typedef cgul_heap_primitives__compare_t cgul_heap_primitives_cxx::compare_t

This typedef is the interface the client must define in order for the cgul_heap_primitives_cxx methods 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

Member Function Documentation

heapify()

static void cgul_heap_primitives_cxx::heapify ( void **  v, size_t  v_count, compare_t  cf  )

inlinestatic

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

Parameters

[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	cf	comparison function

References cgul_heap_primitives__heapify().

shift_down()

static void cgul_heap_primitives_cxx::shift_down ( void **  v, size_t  v_count, size_t  index, int  use_floyds_method, compare_t  cf  )

inlinestatic

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, 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 shift_up() assumes the heap is fully constructed.

Parameters

[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

References cgul_heap_primitives__shift_down().

shift_up()

static void cgul_heap_primitives_cxx::shift_up ( void **  v, size_t  v_count, size_t  index, compare_t  cf  )

inlinestatic

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]	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

References cgul_heap_primitives__shift_up().

---

The documentation for this class was generated from the following file:

• cgul_heap_primitives_cxx.h