binary heap More...

#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_heap_primitives.h"
#include "cgul_vector.h"

Include dependency graph for cgul_heap.h:

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

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_heap *	cgul_heap_t

Functions
CGUL_EXPORT cgul_heap_t	cgul_heap__new (cgul_exception_t *cex, cgul_heap_primitives__compare_t cf)

CGUL_EXPORT cgul_heap_t	cgul_heap__new_from_vector (cgul_exception_t *cex, cgul_vector_t v, cgul_heap_primitives__compare_t cf)

CGUL_EXPORT void	cgul_heap__delete (cgul_heap_t heap)

CGUL_EXPORT void	cgul_heap__free_values (cgul_heap_t heap)

CGUL_EXPORT int	cgul_heap__is_empty (cgul_exception_t *cex, cgul_heap_t heap)

CGUL_EXPORT void	cgul_heap__push (cgul_exception_t cex, cgul_heap_t heap, void value)

CGUL_EXPORT void *	cgul_heap__pop (cgul_exception_t *cex, cgul_heap_t heap)

CGUL_EXPORT void *	cgul_heap__top (cgul_exception_t *cex, cgul_heap_t heap)

CGUL_EXPORT unsigned long int	cgul_heap__get_size (cgul_exception_t *cex, cgul_heap_t heap)

CGUL_EXPORT void	cgul_heap__swap (cgul_exception_t *cex, cgul_heap_t heap1, cgul_heap_t heap2)

Detailed Description

Binary heap implementation. This class can be used to trivially implement a priority queue. By default, this class implements a max-heap but can be used as a min-heap simply by negating the output of the comparison function.

Author: Paul Serice

Typedef Documentation

§ cgul_heap_t

typedef typedefCGUL_BEGIN_C struct cgul_heap* cgul_heap_t

Opaque pointer to a cgul_heap instance.

Function Documentation

§ cgul_heap__new()

CGUL_EXPORT cgul_heap_t cgul_heap__new	(	cgul_exception_t *	cex,
		cgul_heap_primitives__compare_t	cf
	)

Create a new cgul_heap object that maintains heap order using the comparison function cf. The caller is responsible for freeing the object by calling cgul_heap__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Note: cgul_heap is by default a max-heap, but it can be used as a min-heap simply by negating the output of the comparison function.

Parameters

[in,out]	cex	c-style exception
[in]	cf	comparison function

Returns: new cgul_heap instance

See also: cgul_heap__new_from_vector()

§ cgul_heap__new_from_vector()

CGUL_EXPORT cgul_heap_t cgul_heap__new_from_vector	(	cgul_exception_t *	cex,
		cgul_vector_t	v,
		cgul_heap_primitives__compare_t	cf
	)

Create a new cgul_heap object from the vector v. The new heap maintains heap order using the comparison function cf. The caller is responsible for freeing the object by calling cgul_heap__delete(). This class takes ownership of the vector so that calling cgul_heap__delete() also deletes the vector. If memory cannot be allocated, NULL is returned, and an exception is thrown.

Note: cgul_heap is by default a max-heap, but it can be used as a min-heap simply by negating the output of the comparison function.

Note: The asymptotic complexity of this method is O(n) which is more efficient than creating an empty heap and inserting n elements which would be O(n log n).

Parameters

[in,out]	cex	c-style exception
[in]	v	vector
[in]	cf	comparison function

Returns: new cgul_heap instance

Referenced by cgul_heap_cxx::set_obj().

§ cgul_heap__delete()

CGUL_EXPORT void cgul_heap__delete ( cgul_heap_t heap )

This method frees all internally allocated memory. This method does not free the elements stored in the heap. The caller allocated those elements so the caller is responsible for freeing them. Do not try to access heap after calling this method.

Parameters

[in] heap cgul_heap instance

See also: cgul_heap__free_values()

Referenced by cgul_heap_cxx::set_obj(), and cgul_heap_cxx::~cgul_heap_cxx().

§ cgul_heap__free_values()

CGUL_EXPORT void cgul_heap__free_values ( cgul_heap_t heap )

This method calls free() on all the values in the heap heap. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_heap__delete() because it otherwise invalidates the heap. Because this function is basically an extension of cgul_heap__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] heap cgul_heap instance

Referenced by cgul_heap_cxx::free_values().

§ cgul_heap__is_empty()

CGUL_EXPORT int cgul_heap__is_empty	(	cgul_exception_t *	cex,
		cgul_heap_t	heap
	)

Return true if the heap heap is empty.

Parameters

[in]	cex	c-style exception
[in]	heap	`cgul_heap` instance

Returns: whether heap is empty

Referenced by cgul_heap_cxx::is_empty().

§ cgul_heap__push()

CGUL_EXPORT void cgul_heap__push	(	cgul_exception_t *	cex,
		cgul_heap_t	heap,
		void *	value
	)

Push the value value onto the heap heap maintaining heap order using the some comparison function that was passed into the heap constructor. If an error occurs, an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	heap	`cgul_heap` instance
[in]	value	to push onto the heap

Referenced by cgul_heap_cxx::push().

§ cgul_heap__pop()

CGUL_EXPORT void* cgul_heap__pop	(	cgul_exception_t *	cex,
		cgul_heap_t	heap
	)

Pop the top value from the heap heap maintaining heap order using the some comparison function that was passed into the heap constructor. If the heap is empty, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	heap	`cgul_heap` instance

Returns: top value

Referenced by cgul_heap_cxx::pop().

§ cgul_heap__top()

CGUL_EXPORT void* cgul_heap__top	(	cgul_exception_t *	cex,
		cgul_heap_t	heap
	)

Return the top value from the heap heap without removing it from the heap. If the heap is empty, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	heap	`cgul_heap` instance

Returns: top value

Referenced by cgul_heap_cxx::top().

§ cgul_heap__get_size()

CGUL_EXPORT unsigned long int cgul_heap__get_size	(	cgul_exception_t *	cex,
		cgul_heap_t	heap
	)

Return the size of the heap heap. This is a count of the total number of elements stored in the heap.

Parameters

[in]	cex	c-style exception
[in]	heap	`cgul_heap` instance

Returns: size of the heap

Referenced by cgul_heap_cxx::get_size().

§ cgul_heap__swap()

CGUL_EXPORT void cgul_heap__swap	(	cgul_exception_t *	cex,
		cgul_heap_t	heap1,
		cgul_heap_t	heap2
	)

Swap the underlying data for heap1 and heap2. For large heaps, this should be much faster than trying to do the same thing using removes and inserts.

Parameters

[in]	cex	c-style exception
[in]	heap1	first `cgul_heap` instance
[in]	heap2	second `cgul_heap` instance

Referenced by cgul_heap_cxx::swap().

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_heap_t

Function Documentation

§ cgul_heap__new()

§ cgul_heap__new_from_vector()

§ cgul_heap__delete()

§ cgul_heap__free_values()

§ cgul_heap__is_empty()

§ cgul_heap__push()

§ cgul_heap__pop()

§ cgul_heap__top()

§ cgul_heap__get_size()

§ cgul_heap__swap()