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]cexc-style exception
[in]varray of pointers to elements to sort
[in]v_countnumber of elements in v
[in]cfcomparison 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]cexc-style exception
[in]varray of pointers to elements to sort
[in]v_countnumber of elements in v
[in]indexindex of element to be shifted down
[in]use_floyds_methoduse Floyd's Method
[in]cfcomparison 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]cexc-style exception
[in]varray of pointers to elements to sort
[in]v_countnumber of elements in v
[in]indexindex of element to be shifted down
[in]cfcomparison 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]e1first element
[in]e2second element
Returns
result of comparison