updateable priority queue class. unlike most PQ implementations, we need a method to inform the PQ of updated elements thats why we cannot use priority_queue from the STL. maxheap works on an external array of elements T, note that none of the elements of m_arr[0]..m_arr[size-1] are in the heap at the begining. You can insert elements by using maxheap::insert(i); More...

#include <maxheap.h>

Public Member Functions
size_t	arr_size () const
	returns size of external array

void	create (const std::vector< T > &v)

void	create (size_t n, const T *arr_)
	creates the heap on a external array arr_[0]..arr_[n-1]

int	get_max () const
	returns the index in m_arr of maximal element of the heap

size_t	height () const
	returns nr of elements in the heap.

void	insert_item (int i)

bool	is_in (size_t i)

	maxheap ()

	maxheap (const std::vector< T > &v)

	maxheap (size_t n, const T *arr_)

void	print () const

void	remove (int i)
	removes index i in m_arr

int	remove_max ()
	returns the index in m_arr of maximal element of the m_heap and removes it from the m_heap

void	reset ()

void	update (int i)
	update the heap position of array element i (m_arr[i]) use this method if you have changed the value used in operator < of element i.

	~maxheap ()
	deconstructor

Private Member Functions
void	downheap (int i)

int	leftchild (int index) const

	maxheap (const maxheap< T > *other)

void	myswap (int i, int j)

int	parent (int index) const

int	rightchild (int index) const

void	upheap (int i)

Private Attributes
const T *	m_arr

stdvector< int >	m_heap

size_t	m_height

stdvector< int >	m_posinheap

size_t	m_size

Detailed Description

template<typename T>
class ug::maxheap< T >

updateable priority queue class. unlike most PQ implementations, we need a method to inform the PQ of updated elements thats why we cannot use priority_queue from the STL. maxheap works on an external array of elements T, note that none of the elements of m_arr[0]..m_arr[size-1] are in the heap at the begining. You can insert elements by using maxheap::insert(i);

Note: a radix heap would be faster for some applications.

Parameters

T	type of elements in the maxheap. Have to support bool operator <(const T &a, const T &b)

Constructor & Destructor Documentation

◆ maxheap() [1/4]

template<typename T >

ug::maxheap< T >::maxheap ( const maxheap< T > * other )

private

◆ maxheap() [2/4]

template<typename T >

ug::maxheap< T >::maxheap ( )

inline

References ug::maxheap< T >::m_arr, ug::maxheap< T >::m_height, and ug::maxheap< T >::m_size.

◆ maxheap() [3/4]

template<typename T >

ug::maxheap< T >::maxheap	(	size_t	n,
		const T *	arr_
	)

inline

constructor

Parameters

n	maximal number of elements
arr_	array with elements which are to compare. note that non of these are in the heap in the beginning

References ug::maxheap< T >::create(), ug::maxheap< T >::m_heap, ug::maxheap< T >::m_posinheap, and ug::maxheap< T >::m_size.

◆ maxheap() [4/4]

template<typename T >

ug::maxheap< T >::maxheap ( const std::vector< T > & v )

inline

References ug::maxheap< T >::create(), ug::maxheap< T >::m_heap, ug::maxheap< T >::m_posinheap, and ug::maxheap< T >::m_size.

◆ ~maxheap()

template<typename T >

ug::maxheap< T >::~maxheap ( )

inline

deconstructor

Member Function Documentation

◆ arr_size()

template<typename T >

size_t ug::maxheap< T >::arr_size ( ) const

inline

returns size of external array

References ug::maxheap< T >::m_size.

◆ create() [1/2]

template<typename T >

void ug::maxheap< T >::create ( const std::vector< T > & v )

inline

References ug::maxheap< T >::create().

◆ create() [2/2]

template<typename T >

void ug::maxheap< T >::create	(	size_t	n,
		const T *	arr_
	)

inline

creates the heap on a external array arr_[0]..arr_[n-1]

create

References ug::maxheap< T >::m_arr, ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_posinheap, and ug::maxheap< T >::m_size.

Referenced by ug::maxheap< T >::create(), ug::maxheap< T >::maxheap(), and ug::maxheap< T >::maxheap().

◆ downheap()

template<typename T >

void ug::maxheap< T >::downheap ( int i )

inlineprivate

Parameters

i	index in m_arr for which to downheap

References ug::maxheap< T >::leftchild(), ug::maxheap< T >::m_arr, ug::maxheap< T >::m_posinheap, ug::maxheap< T >::myswap(), and ug::maxheap< T >::rightchild().

Referenced by ug::maxheap< T >::remove(), and ug::maxheap< T >::update().

◆ get_max()

template<typename T >

int ug::maxheap< T >::get_max ( ) const

inline

returns the index in m_arr of maximal element of the heap

References ug::maxheap< T >::m_heap.

◆ height()

template<typename T >

size_t ug::maxheap< T >::height ( ) const

inline

returns nr of elements in the heap.

References ug::maxheap< T >::m_height.

◆ insert_item()

template<typename T >

void ug::maxheap< T >::insert_item ( int i )

inline

insertItem inserts Item m_arr[i] (see constructor) into the heap

Parameters

i	index of item in m_arr

References ug::maxheap< T >::is_in(), ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_posinheap, ug::maxheap< T >::m_size, UG_ASSERT, and ug::maxheap< T >::upheap().

◆ is_in()

template<typename T >

bool ug::maxheap< T >::is_in ( size_t i )

inline

References ug::maxheap< T >::m_posinheap.

Referenced by ug::maxheap< T >::insert_item(), ug::maxheap< T >::remove(), and ug::maxheap< T >::update().

◆ leftchild()

template<typename T >

int ug::maxheap< T >::leftchild ( int index ) const

inlineprivate

returns the index in m_arr of the left child of i all indices in m_arr, NOT in m_heap

Parameters

index index in m_arr of element

Returns: returns index in m_arr of the left child

References ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_posinheap, and p.

Referenced by ug::maxheap< T >::downheap().

◆ myswap()

template<typename T >

void ug::maxheap< T >::myswap	(	int	i,
		int	j
	)

inlineprivate

swaps elements i and j of array m_posinheap and their counterparts in m_heap

References ug::maxheap< T >::m_heap, and ug::maxheap< T >::m_posinheap.

Referenced by ug::maxheap< T >::downheap(), ug::maxheap< T >::remove(), and ug::maxheap< T >::upheap().

◆ parent()

template<typename T >

int ug::maxheap< T >::parent ( int index ) const

inlineprivate

returns the index in m_arr of the parent of i all indices in m_arr, NOT in m_heap

Parameters

index index in m_arr of element

Returns: returns index in m_arr of the parent

References ug::maxheap< T >::m_heap, ug::maxheap< T >::m_posinheap, and p.

Referenced by ug::maxheap< T >::print(), ug::maxheap< T >::update(), and ug::maxheap< T >::upheap().

◆ print()

template<typename T >

void ug::maxheap< T >::print ( ) const

inline

debug print output

References ug::maxheap< T >::m_arr, ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_size, and ug::maxheap< T >::parent().

◆ remove()

template<typename T >

void ug::maxheap< T >::remove ( int i )

inline

removes index i in m_arr

References ug::maxheap< T >::downheap(), ug::maxheap< T >::is_in(), ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_posinheap, and ug::maxheap< T >::myswap().

Referenced by ug::maxheap< T >::remove_max().

◆ remove_max()

template<typename T >

int ug::maxheap< T >::remove_max ( )

inline

returns the index in m_arr of maximal element of the m_heap and removes it from the m_heap

References ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::remove(), and UG_ASSERT.

◆ reset()

template<typename T >

void ug::maxheap< T >::reset ( )

inline

reset set m_height 0 (= remove all items from the heap)

References ug::maxheap< T >::m_height.

◆ rightchild()

template<typename T >

int ug::maxheap< T >::rightchild ( int index ) const

inlineprivate

returns the index in m_arr of the right child of i all indices in m_arr, NOT in m_heap

Parameters

index index in m_arr of element

Returns: returns index in m_arr of the right child

References ug::maxheap< T >::m_heap, ug::maxheap< T >::m_height, ug::maxheap< T >::m_posinheap, and p.

Referenced by ug::maxheap< T >::downheap().

◆ update()

template<typename T >

void ug::maxheap< T >::update ( int i )

inline

update the heap position of array element i (m_arr[i]) use this method if you have changed the value used in operator < of element i.

Parameters

i	index in m_arr for which to update

References ug::maxheap< T >::downheap(), ug::maxheap< T >::is_in(), ug::maxheap< T >::m_arr, ug::maxheap< T >::parent(), and ug::maxheap< T >::upheap().

◆ upheap()

template<typename T >

void ug::maxheap< T >::upheap ( int i )

inlineprivate

Parameters

i	index in m_arr for which to upheap

See also: update

References ug::maxheap< T >::m_arr, ug::maxheap< T >::m_posinheap, ug::maxheap< T >::myswap(), and ug::maxheap< T >::parent().

Referenced by ug::maxheap< T >::insert_item(), and ug::maxheap< T >::update().

Member Data Documentation

◆ m_arr

template<typename T >

const T* ug::maxheap< T >::m_arr

private

Referenced by ug::maxheap< T >::create(), ug::maxheap< T >::downheap(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::print(), ug::maxheap< T >::update(), and ug::maxheap< T >::upheap().

◆ m_heap

template<typename T >

stdvector<int> ug::maxheap< T >::m_heap

private

Referenced by ug::maxheap< T >::create(), ug::maxheap< T >::get_max(), ug::maxheap< T >::insert_item(), ug::maxheap< T >::leftchild(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::myswap(), ug::maxheap< T >::parent(), ug::maxheap< T >::print(), ug::maxheap< T >::remove(), ug::maxheap< T >::remove_max(), and ug::maxheap< T >::rightchild().

◆ m_height

template<typename T >

size_t ug::maxheap< T >::m_height

private

Referenced by ug::maxheap< T >::create(), ug::maxheap< T >::height(), ug::maxheap< T >::insert_item(), ug::maxheap< T >::leftchild(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::print(), ug::maxheap< T >::remove(), ug::maxheap< T >::remove_max(), ug::maxheap< T >::reset(), and ug::maxheap< T >::rightchild().

◆ m_posinheap

template<typename T >

stdvector<int> ug::maxheap< T >::m_posinheap

private

Referenced by ug::maxheap< T >::create(), ug::maxheap< T >::downheap(), ug::maxheap< T >::insert_item(), ug::maxheap< T >::is_in(), ug::maxheap< T >::leftchild(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::myswap(), ug::maxheap< T >::parent(), ug::maxheap< T >::remove(), ug::maxheap< T >::rightchild(), and ug::maxheap< T >::upheap().

◆ m_size

template<typename T >

size_t ug::maxheap< T >::m_size

private

Referenced by ug::maxheap< T >::arr_size(), ug::maxheap< T >::create(), ug::maxheap< T >::insert_item(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::maxheap(), ug::maxheap< T >::maxheap(), and ug::maxheap< T >::print().

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

ugbase/lib_algebra/common/heap/maxheap.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ maxheap() [1/4]

◆ maxheap() [2/4]

◆ maxheap() [3/4]

◆ maxheap() [4/4]

◆ ~maxheap()

Member Function Documentation

◆ arr_size()

◆ create() [1/2]

◆ create() [2/2]

◆ downheap()

◆ get_max()

◆ height()

◆ insert_item()

◆ is_in()

◆ leftchild()

◆ myswap()

◆ parent()

◆ print()

◆ remove()

◆ remove_max()

◆ reset()

◆ rightchild()

◆ update()

◆ upheap()

Member Data Documentation

◆ m_arr

◆ m_heap

◆ m_height

◆ m_posinheap

◆ m_size