libnabo
1.0.1
|
balanced-tree implementation of heap More...
#include <index_heap.h>
Classes | |
struct | Entry |
an entry of the heap tree More... | |
Public Types | |
typedef IT | Index |
type of an index | |
typedef VT | Value |
type of a value | |
typedef std::vector< Entry > | Entries |
vector of entry, type for the storage of the tree | |
typedef Eigen::Matrix< Index, Eigen::Dynamic, 1 > | IndexVector |
vector of indices | |
typedef Eigen::Matrix< Value, Eigen::Dynamic, 1 > | ValueVector |
vector of values | |
Public Member Functions | |
IndexHeapSTL (const size_t size) | |
Constructor. | |
void | reset () |
reset to the empty heap | |
const VT & | headValue () const |
get the largest value of the heap | |
void | replaceHead (const Index index, const Value value) |
replace the largest value of the heap | |
void | sort () |
sort the entries, from the smallest to the largest | |
template<typename DI , typename DV > | |
void | getData (const Eigen::MatrixBase< DI > &indices, const Eigen::MatrixBase< DV > &values) const |
get the data from the heap | |
Public Attributes | |
Entries | data |
storage for the tree | |
const VT & | headValueRef |
reference to the largest value in the tree, to optimise access speed | |
const Entries::iterator | insertIt |
iterator to the insertion position in the tree, to optimise access speed |
balanced-tree implementation of heap
It uses a binary heap, which provides replacement in O(log(n)), however the constant overhead is significative.
Nabo::IndexHeapSTL< IT, VT >::IndexHeapSTL | ( | const size_t | size | ) | [inline] |
Constructor.
size | number of elements in the heap |
void Nabo::IndexHeapSTL< IT, VT >::getData | ( | const Eigen::MatrixBase< DI > & | indices, |
const Eigen::MatrixBase< DV > & | values | ||
) | const [inline] |
get the data from the heap
indices | index vector |
values | value vector |
const VT& Nabo::IndexHeapSTL< IT, VT >::headValue | ( | ) | const [inline] |
get the largest value of the heap
void Nabo::IndexHeapSTL< IT, VT >::replaceHead | ( | const Index | index, |
const Value | value | ||
) | [inline] |
replace the largest value of the heap
index | new point index |
value | new distance value |