JASS::heap< TYPE > Class Template Reference

A bare-bones implementaiton of a min-heap over an array passed by the caller. More...

#include <heap.h>

Collaboration diagram for JASS::heap< TYPE >:

Public Member Functions
	heap (TYPE *array, size_t size=0)
	Constructor. More...
void	set_top_k (size_t size)
	change maximum number of elements in the array More...
forceinline void	make_heap (void)
	build the heap
forceinline void	push_back (TYPE key)
	Add and element to the heap. More...
int64_t	find (const TYPE &key) const
	Find an instance of key in the heap and return its index into array[]. More...
forceinline void	promote (TYPE key, size_t position)
	Key has changed its value so re-build the heap from that point onwards. More...

Static Public Member Functions
static void	unittest (void)
	Unit test this class.

Protected Member Functions
forceinline size_t	left_of (size_t position)
	Return the index of the left element of the heap given the current position in the heap. More...
forceinline size_t	right_of (size_t position)
	Return the index of the right element of the heap given the current position in the heap. More...
void	heapify (size_t position)
	Recurively build the heap. More...
void	insert_from (TYPE key, size_t position=0)
	Add and element to the heap after the given position. More...

Protected Attributes
TYPE *	array
	The array to build the heap over.
size_t	size
	The maximum size of the heap.

Detailed Description

template<typename TYPE>
class JASS::heap< TYPE >

A bare-bones implementaiton of a min-heap over an array passed by the caller.

Template Parameters

TYPE	The type to build the heap over (normall a pointer type).

Constructor & Destructor Documentation

heap()

template<typename TYPE>

JASS::heap< TYPE >::heap ( TYPE *  array, size_t  size = 0  )

inline

Constructor.

Parameters

array	[in] The array to maintain the heap over
size	[in] The maximum number of elements in the array (the size of the heap)

Member Function Documentation

find()

template<typename TYPE>

int64_t JASS::heap< TYPE >::find ( const TYPE &  key ) const

inline

Find an instance of key in the heap and return its index into array[].

Parameters

key	[in] The key to look for.

Returns

The index into array[] of an instance of key, or -1 if key cannot be found in the heap.

heapify()

template<typename TYPE>

void JASS::heap< TYPE >::heapify ( size_t  position )

inlineprotected

Recurively build the heap.

Parameters

position

[in] where, in the array, to build the heap

insert_from()

template<typename TYPE>

void JASS::heap< TYPE >::insert_from ( TYPE  key, size_t  position = 0  )

inlineprotected

Add and element to the heap after the given position.

Parameters

key	[in] The element to add to the heap
position	[in] The element to start looking from.

This method does not check to see if the element is already in the heap or that the element should be in the heap (i.e. > smallest).

left_of()

template<typename TYPE>

forceinline size_t JASS::heap< TYPE >::left_of ( size_t  position )

inlineprotected

Return the index of the left element of the heap given the current position in the heap.

Parameters

position

[in] current position in the heap.

Returns

index of left of position.

promote()

template<typename TYPE>

forceinline void JASS::heap< TYPE >::promote ( TYPE  key, size_t  position  )

inline

Key has changed its value so re-build the heap from that point onwards.

Parameters

key	[in] The element that has changed

push_back()

template<typename TYPE>

forceinline void JASS::heap< TYPE >::push_back ( TYPE  key )

inline

Add and element to the heap.

Parameters

key	[in] The element to add to the heap

This method does not check to see if the element is already in the heap or that the element should be in the heap (i.e. > smallest).

right_of()

template<typename TYPE>

forceinline size_t JASS::heap< TYPE >::right_of ( size_t  position )

inlineprotected

Return the index of the right element of the heap given the current position in the heap.

Parameters

position

[in] current position in the heap.

Returns

index of right of position.

set_top_k()

template<typename TYPE>

void JASS::heap< TYPE >::set_top_k ( size_t  size )

inline

change maximum number of elements in the array

Parameters

size	[in] The maximum number of elements in the array (the size of the heap)

---

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

• source/heap.h