Heap realized by a data array. More...

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

Inheritance diagram for ogdf::BinaryHeap< T, C >:

Classes
struct	HeapEntry

Public Member Functions
	BinaryHeap (const C &comp=C(), int initialSize=128)
	Initializes an empty binary heap.

virtual	~BinaryHeap ()

int	capacity () const
	Returns the current size.

void	clear ()
	Reinitializes the data structure.

void	decrease (int *handle, const T &value) override
	Decreases a single value.

bool	empty () const
	Returns true iff the heap is empty.

void	pop () override
	Removes the topmost value from the heap.

int *	push (const T &value) override
	Inserts a value into the heap.

int	size () const
	Returns the number of stored elements.

const T &	top () const override
	Returns the topmost value in the heap.

const T &	value (int *handle) const override
	Returns the value of that handle.

Public Member Functions inherited from ogdf::HeapBase< IMPL, H, T, C >
	HeapBase (const C &comp=C())

virtual const C &	comparator () const
	Returns the comparator used to sort the values in the heap.

virtual void	decrease (Handle handle, const T &value)=0
	Decreases a single value.

virtual void	merge (IMPL &other)
	Merges in values of `other` heap.

virtual const T &	value (const Handle handle) const =0
	Returns the value of that handle.

Private Types
using	base_type = HeapBase< BinaryHeap< T, C >, int, T, C >

Private Member Functions
int	arrayBound (int arraySize)

bool	hasLeft (int num)
	Returns true if left child exists.

bool	hasRight (int num)
	Returns true if right child exists.

int	higherArrayBound (int arraySize)

int	higherArraySize (int arraySize)

void	init (int initialSize)

int	leftChildIndex (int num)
	Array index of left child.

int	lowerArrayBound (int arraySize)

int	lowerArraySize (int arraySize)

int	parentIndex (int num)
	Array index of parent node.

int	rightChildIndex (int num)
	Array index of right child.

void	siftDown (int pos)
	Establishes heap property by moving element down in heap if necessary.

void	siftUp (int pos)
	Establishes heap property by moving element up in heap if necessary.

Private Attributes
int	m_arraySize

HeapEntry *	m_heapArray

int	m_initialSize

int	m_size

Additional Inherited Members
Public Types inherited from ogdf::HeapBase< IMPL, H, T, C >
using	Handle = H *
	The type of handle used to identify stored values.

Detailed Description

template<typename T, typename C = std::less<T>>
class ogdf::BinaryHeap< T, C >

Heap realized by a data array.

This heap implementation does not support merge operations.

Template Parameters

T	Denotes value type of inserted elements.
C	Denotes comparison functor determining value ordering.

Definition at line 47 of file BinaryHeap.h.

Member Typedef Documentation

◆ base_type

template<typename T , typename C = std::less<T>>

using ogdf::BinaryHeap< T, C >::base_type = HeapBase<BinaryHeap<T, C>, int, T, C>

private

Definition at line 48 of file BinaryHeap.h.

Constructor & Destructor Documentation

◆ BinaryHeap()

template<typename T , typename C >

ogdf::BinaryHeap< T, C >::BinaryHeap	(	const C &	comp = `C()`,
		int	initialSize = `128`
	)

explicit

Initializes an empty binary heap.

Parameters

comp	Comparison functor determining value ordering.
initialSize	The intial capacity of this heap. Used to allocate an adequate amount of memory.

Definition at line 279 of file BinaryHeap.h.

◆ ~BinaryHeap()

template<typename T , typename C = std::less<T>>

virtual ogdf::BinaryHeap< T, C >::~BinaryHeap ( )

inlinevirtual

Definition at line 59 of file BinaryHeap.h.

Member Function Documentation

◆ arrayBound()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::arrayBound ( int arraySize )

inlineprivate

Definition at line 160 of file BinaryHeap.h.

◆ capacity()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::capacity ( ) const

inline

Returns the current size.

Definition at line 106 of file BinaryHeap.h.

◆ clear()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::clear ( )

Reinitializes the data structure.

Deletes the array and reallocates it with size that was passed at construction time.

Definition at line 295 of file BinaryHeap.h.

◆ decrease()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::decrease	(	int *	handle,
		const T &	value
	)

override

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

Definition at line 261 of file BinaryHeap.h.

◆ empty()

template<typename T , typename C = std::less<T>>

bool ogdf::BinaryHeap< T, C >::empty ( ) const

inline

Returns true iff the heap is empty.

Definition at line 112 of file BinaryHeap.h.

◆ hasLeft()

template<typename T , typename C = std::less<T>>

bool ogdf::BinaryHeap< T, C >::hasLeft ( int num )

inlineprivate

Returns true if left child exists.

Definition at line 147 of file BinaryHeap.h.

◆ hasRight()

template<typename T , typename C = std::less<T>>

bool ogdf::BinaryHeap< T, C >::hasRight ( int num )

inlineprivate

Returns true if right child exists.

Definition at line 153 of file BinaryHeap.h.

◆ higherArrayBound()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::higherArrayBound ( int arraySize )

inlineprivate

Definition at line 162 of file BinaryHeap.h.

◆ higherArraySize()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::higherArraySize ( int arraySize )

inlineprivate

Definition at line 164 of file BinaryHeap.h.

◆ init()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::init ( int initialSize )

private

Definition at line 284 of file BinaryHeap.h.

◆ leftChildIndex()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::leftChildIndex ( int num )

inlineprivate

Array index of left child.

Definition at line 135 of file BinaryHeap.h.

◆ lowerArrayBound()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::lowerArrayBound ( int arraySize )

inlineprivate

Definition at line 166 of file BinaryHeap.h.

◆ lowerArraySize()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::lowerArraySize ( int arraySize )

inlineprivate

Definition at line 168 of file BinaryHeap.h.

◆ parentIndex()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::parentIndex ( int num )

inlineprivate

Array index of parent node.

Definition at line 129 of file BinaryHeap.h.

◆ pop()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::pop ( )

overridevirtual

Removes the topmost value from the heap.

Implements ogdf::HeapBase< IMPL, H, T, C >.

Definition at line 233 of file BinaryHeap.h.

◆ push()

template<typename T , typename C >

int * ogdf::BinaryHeap< T, C >::push ( const T & value )

overridevirtual

Inserts a value into the heap.

Parameters

value The value to be inserted

Returns: A handle to access and modify the value

Implements ogdf::HeapBase< IMPL, H, T, C >.

Definition at line 197 of file BinaryHeap.h.

◆ rightChildIndex()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::rightChildIndex ( int num )

inlineprivate

Array index of right child.

Definition at line 141 of file BinaryHeap.h.

◆ siftDown()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::siftDown ( int pos )

private

Establishes heap property by moving element down in heap if necessary.

Definition at line 329 of file BinaryHeap.h.

◆ siftUp()

template<typename T , typename C >

void ogdf::BinaryHeap< T, C >::siftUp ( int pos )

private

Establishes heap property by moving element up in heap if necessary.

Definition at line 305 of file BinaryHeap.h.

◆ size()

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::size ( ) const

inline

Returns the number of stored elements.

Definition at line 109 of file BinaryHeap.h.

◆ top()

template<typename T , typename C >

const T & ogdf::BinaryHeap< T, C >::top ( ) const

overridevirtual

Returns the topmost value in the heap.

Returns: the topmost value

Implements ogdf::HeapBase< IMPL, H, T, C >.

Definition at line 191 of file BinaryHeap.h.

◆ value()

template<typename T , typename C >

const T & ogdf::BinaryHeap< T, C >::value ( int * handle ) const

override

Returns the value of that handle.

Parameters

handle The handle

Returns: The value

Definition at line 270 of file BinaryHeap.h.

Member Data Documentation

◆ m_arraySize

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::m_arraySize

private

Definition at line 184 of file BinaryHeap.h.

◆ m_heapArray

template<typename T , typename C = std::less<T>>

HeapEntry* ogdf::BinaryHeap< T, C >::m_heapArray

private

Definition at line 178 of file BinaryHeap.h.

◆ m_initialSize

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::m_initialSize

private

Definition at line 187 of file BinaryHeap.h.

◆ m_size

template<typename T , typename C = std::less<T>>

int ogdf::BinaryHeap< T, C >::m_size

private

Definition at line 181 of file BinaryHeap.h.

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

include/ogdf/basic/heap/BinaryHeap.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_type

Constructor & Destructor Documentation

◆ BinaryHeap()

◆ ~BinaryHeap()

Member Function Documentation

◆ arrayBound()

◆ capacity()

◆ clear()

◆ decrease()

◆ empty()

◆ hasLeft()

◆ hasRight()

◆ higherArrayBound()

◆ higherArraySize()

◆ init()

◆ leftChildIndex()

◆ lowerArrayBound()

◆ lowerArraySize()

◆ parentIndex()

◆ pop()

◆ push()

◆ rightChildIndex()

◆ siftDown()

◆ siftUp()

◆ size()

◆ top()

◆ value()

Member Data Documentation

◆ m_arraySize

◆ m_heapArray

◆ m_initialSize

◆ m_size

Open
Graph Drawing
Framework