Binary min-heap with index lookups. More...

#include <heap_indexed.h>

Public Member Functions
void	reset ()

size_t	size () const

bool	contains (size_t idx) const

KeyType	key_of (size_t idx) const

void	up_heap (size_t idx, KeyType key, size_t loc)

void	down_heap (size_t idx, KeyType key, size_t loc)

void	insert (size_t idx, KeyType key)

void	update (size_t idx, KeyType key)

void	remove (size_t idx)

KeyType	top_key () const

size_t	top_idx () const

void	remove_min ()

void	print () const

Detailed Description

template<typename KeyType>
class pr_bgl::heap_indexed< KeyType >

Binary min-heap with index lookups.

The HeapIndexed class implements a binary min-heap with index lookups. Elements are identified with an index value (e.g. [0,num_vertices)). The heap also maintains a vector backing, wich each element at a particular location.

Todo:: this may duplicate functionality implemented in BGL.

KeyType: e.g. double

for example:
backing: [ (??,?), (0.3,3), (0.5,7), (0.7,2), (0.6,1) ]
locs: [0, 4, 3, 1, 0, 0, 0, 2]

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

pr_bgl/include/pr_bgl/heap_indexed.h

Public Member Functions

Detailed Description

template<typename KeyType> class pr_bgl::heap_indexed< KeyType >

template<typename KeyType>
class pr_bgl::heap_indexed< KeyType >