ogdf::HeapBase< IMPL, H, T, C > Class Template Reference

Common interface for all heap classes. More...

#include <ogdf/basic/heap/HeapBase.h>

Public Types
using	Handle = H *
	The type of handle used to identify stored values. More...

Public Member Functions
	HeapBase (const C &comp=C())
virtual const C &	comparator () const
	Returns the comparator used to sort the values in the heap. More...
virtual void	decrease (Handle handle, const T &value)=0
	Decreases a single value. More...
virtual void	merge (IMPL &other)
	Merges in values of other heap. More...
virtual void	pop ()=0
	Removes the topmost value from the heap. More...
virtual Handle	push (const T &value)=0
	Inserts a value into the heap. More...
virtual const T &	top () const =0
	Returns the topmost value in the heap. More...
virtual const T &	value (const Handle handle) const =0
	Returns the value of that handle. More...

Private Attributes
C	m_comp

Detailed Description

template<typename IMPL, typename H, typename T, typename C>
class ogdf::HeapBase< IMPL, H, T, C >

Common interface for all heap classes.

Template Parameters

IMPL	The type of heap.
H	The type of handle to use. Such a handle will be given to the user for each pushed value.
T	The type of values to be stored.
C	The comparator used to order the stored values.

Definition at line 48 of file HeapBase.h.

Member Typedef Documentation

Handle

template<typename IMPL , typename H , typename T , typename C >

using ogdf::HeapBase< IMPL, H, T, C >::Handle = H*

The type of handle used to identify stored values.

The handle type accessible from outside of the heap will always be a pointer.

Definition at line 56 of file HeapBase.h.

Constructor & Destructor Documentation

HeapBase()

template<typename IMPL , typename H , typename T , typename C >

ogdf::HeapBase< IMPL, H, T, C >::HeapBase ( const C &  comp = C() )

inlineexplicit

Definition at line 58 of file HeapBase.h.

Member Function Documentation

comparator()

template<typename IMPL , typename H , typename T , typename C >

virtual const C& ogdf::HeapBase< IMPL, H, T, C >::comparator ( ) const

inlinevirtual

Returns the comparator used to sort the values in the heap.

Returns

The comparator for sorting the heaps values

Definition at line 65 of file HeapBase.h.

decrease()

template<typename IMPL , typename H , typename T , typename C >

virtual void ogdf::HeapBase< IMPL, H, T, C >::decrease ( Handle  handle, const T &  value  )

pure virtual

Decreases a single value.

Parameters

handle	The handle of the value to be decreased
value	The decreased value. This must be less than the former value

Implemented in ogdf::BinaryHeap< T, C >.

merge()

template<typename IMPL , typename H , typename T , typename C >

void ogdf::HeapBase< IMPL, H, T, C >::merge ( IMPL &  other )

virtual

Merges in values of other heap.

After merge other heap becomes empty and is valid for further usage.

Parameters

other

A heap to be merged in.

Reimplemented in ogdf::PairingHeap< T, C >.

Definition at line 114 of file HeapBase.h.

pop()

template<typename IMPL , typename H , typename T , typename C >

virtual void ogdf::HeapBase< IMPL, H, T, C >::pop ( )

pure virtual

Removes the topmost value from the heap.

Implemented in ogdf::FibonacciHeap< T, C >, ogdf::RMHeap< T, C >, ogdf::BinomialHeap< T, C >, ogdf::PairingHeap< T, C >, and ogdf::BinaryHeap< T, C >.

push()

template<typename IMPL , typename H , typename T , typename C >

virtual Handle ogdf::HeapBase< IMPL, H, T, C >::push ( const T &  value )

pure virtual

Inserts a value into the heap.

Parameters

value

The value to be inserted

Returns

A handle to access and modify the value

Implemented in ogdf::FibonacciHeap< T, C >, ogdf::RMHeap< T, C >, ogdf::BinomialHeap< T, C >, ogdf::PairingHeap< T, C >, and ogdf::BinaryHeap< T, C >.

top()

template<typename IMPL , typename H , typename T , typename C >

virtual const T& ogdf::HeapBase< IMPL, H, T, C >::top ( ) const

pure virtual

Returns the topmost value in the heap.

Returns

the topmost value

value()

template<typename IMPL , typename H , typename T , typename C >

virtual const T& ogdf::HeapBase< IMPL, H, T, C >::value ( const Handle  handle ) const

pure virtual

Returns the value of that handle.

Parameters

handle

The handle

Returns

The value

Implemented in ogdf::BinaryHeap< T, C >.

Member Data Documentation

m_comp

template<typename IMPL , typename H , typename T , typename C >

C ogdf::HeapBase< IMPL, H, T, C >::m_comp

private

Definition at line 49 of file HeapBase.h.

---

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

• include/ogdf/basic/heap/HeapBase.h