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 49 of file heap.h.

Constructor & Destructor Documentation

template<typename T>

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

inline

Constructor.

Params: size = heap size

Definition at line 74 of file heap.h.

Member Function Documentation

template<typename T>

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

inline

Returns: heap size

Definition at line 94 of file heap.h.

template<typename T>

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

inline

Clears the heap.

Definition at line 112 of file heap.h.

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 104 of file heap.h.

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 135 of file heap.h.

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 158 of file heap.h.

template<typename T>

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

inline

Returns: heap size

Definition at line 85 of file heap.h.

Member Data Documentation

template<typename T>

int rtflann::Heap< T >::count

private

Number of element in the heap

Definition at line 62 of file heap.h.

template<typename T>

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

private

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

Definition at line 56 of file heap.h.

template<typename T>

int rtflann::Heap< T >::length

private

Definition at line 57 of file heap.h.

---

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

• heap.h