Classes
struct	extended_element
	store per element, whether it is empty and a link to the next empty element or to the heap location More...

Public Member Functions
	dynamic_priority_queue ()
	empty construction

void	clear ()
	remove all elements

bool	empty () const
	check if heap is empty

size_t	size () const
	return the number of elements in the heap

size_t	size_of_element_container () const
	return the number of elements in the heap

queue interface
unsigned int	top () const
	return the top element

void	pop ()
	remove top element

int	extract ()
	extract top element

dynamic element access
bool	is_empty (unsigned int idx) const

const element_type &	operator[] (unsigned int idx) const

element_type &	operator[] (unsigned int idx)

unsigned int	insert (const element_type &e)
	insert the given element and return its index in the element container

void	update (unsigned int idx)
	update after a change to the predicate

void	remove (unsigned int idx)
	remove element at location idx

Protected Member Functions
bool	valid (unsigned int hp) const
	check if a position is outside of range

void	updateLink (unsigned int hp)
	make sure that the link for hp is ok

bool	isBetter (unsigned int hp1, unsigned int hp2) const
	check if hp1 is less than hp2, if true, exchange elements

bool	exchangeIfBetter (unsigned int hp1, unsigned int hp2)
	check if hp1 is less than hp2, if true, exchange elements

void	move (unsigned int hp1, unsigned int hp2)
	move one element to another position, that should be empty

void	removeHeap (unsigned int hp)
	remove an element on a certain heap pos

void	positionDownward (unsigned int &hp)
	move an element downward to the correct position

bool	positionUpward (unsigned int &hp)
	move an element upward to the correct position

Protected Attributes
std::vector< extended_element >	elements
	container for elements

int	last_empty_element
	store index of last empty element or -1 if there is non

std::vector< unsigned int >	heap
	store indices to the elements on the heap

Detailed Description

IndexHeap is a heap that allows changing of the elements

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

Classes