cvflann::Heap< T > Class Template Reference

#include <heap.h>

List of all members.

Public Member Functions
void	clear ()
bool	empty ()
	Heap (int size)
void	heapify (int parent)
void	insert (T value)
bool	popMin (T &value)
int	size ()
	~Heap ()
Private Attributes
int	count
T *	heap
int	length

---

Detailed Description

template<typename T>
class cvflann::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. Note that a heap uses 1-based indexing to allow for power-of-2 location of parents and children. We ignore element 0 of Heap array.

Definition at line 51 of file heap.h.

---

Constructor & Destructor Documentation

template<typename T>

cvflann::Heap< T >::Heap

(

int

size

)

[inline]

Constructor.

Params: size = heap size

Definition at line 75 of file heap.h.

template<typename T>

cvflann::Heap< T >::~Heap

(

)

[inline]

Destructor.

Definition at line 87 of file heap.h.

---

Member Function Documentation

template<typename T>

void cvflann::Heap< T >::clear

(

)

[inline]

Clears the heap.

Definition at line 114 of file heap.h.

template<typename T>

bool cvflann::Heap< T >::empty

(

)

[inline]

Tests if the heap is empty

Returns: true is heap empty, false otherwise

Definition at line 106 of file heap.h.

template<typename T>

void cvflann::Heap< T >::heapify

(

int

parent

)

[inline]

Reorganizes the heap (a parent is smaller than its children) starting with a node.

Params: parent = node form which to start heap reorganization.

Definition at line 182 of file heap.h.

template<typename T>

void cvflann::Heap< T >::insert

(

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

template<typename T>

bool cvflann::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 cvflann::Heap< T >::size

(

)

[inline]

Returns: heap size

Definition at line 96 of file heap.h.

---

Member Data Documentation

template<typename T>

int cvflann::Heap< T >::count [private]

Number of element in the heap

Definition at line 63 of file heap.h.

template<typename T>

T* cvflann::Heap< T >::heap [private]

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

Definition at line 57 of file heap.h.

template<typename T>

int cvflann::Heap< T >::length [private]

Definition at line 58 of file heap.h.

---

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

• heap.h