rtflann::Heap< T > Class Template Reference

#include <heap.h>

Classes
struct	CompareT

Public Member Functions
int	capacity ()
void	clear ()
bool	empty ()
	Heap (int size)
void	insert (const T &value)
bool	popMin (T &value)
int	size ()

Private Attributes
int	count
std::vector< T >	heap
int	length

Detailed Description

template<typename T>
class rtflann::Heap< T >

Priority Queue Implementation

The priority queue is implemented with a heap. A heap is a complete (full) binary tree in which each parent is less than both of its children, but the order of the children is unspecified.

Definition at line 77 of file heap.h.

Constructor & Destructor Documentation

Heap()

template<typename T >

rtflann::Heap< T >::Heap ( int  size )

inline

Constructor.

Params: size = heap size

Definition at line 130 of file heap.h.

Member Function Documentation

capacity()

template<typename T >

int rtflann::Heap< T >::capacity ( )

inline

Returns: heap size

Definition at line 150 of file heap.h.

clear()

template<typename T >

void rtflann::Heap< T >::clear ( )

inline

Clears the heap.

Definition at line 168 of file heap.h.

empty()

template<typename T >

bool rtflann::Heap< T >::empty ( )

inline

Tests if the heap is empty

Returns: true is heap empty, false otherwise

Definition at line 160 of file heap.h.

insert()

template<typename T >

void rtflann::Heap< T >::insert ( const T &  value )

inline

Insert a new element in the heap.

We select the next empty leaf node, and then keep moving any larger parents down until the right location is found to store this element.

Params: value = the new element to be inserted in the heap

Definition at line 194 of file heap.h.

popMin()

template<typename T >

bool rtflann::Heap< T >::popMin ( T &  value )

inline

Returns the node of minimum value from the heap (top of the heap).

Params: value = out parameter used to return the min element Returns: false if heap empty

Definition at line 217 of file heap.h.

size()

template<typename T >

int rtflann::Heap< T >::size ( )

inline

Returns: heap size

Definition at line 141 of file heap.h.

Member Data Documentation

count

template<typename T >

int rtflann::Heap< T >::count

private

Number of element in the heap

Definition at line 118 of file heap.h.

heap

template<typename T >

std::vector<T> rtflann::Heap< T >::heap

private

Storage array for the heap. Type T must be comparable.

Definition at line 112 of file heap.h.

length

template<typename T >

int rtflann::Heap< T >::length

private

Definition at line 113 of file heap.h.

---

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

• heap.h