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. More...

virtual	~BinaryHeap ()

int	capacity () const
	Returns the current size. More...

void	clear ()
	Reinitializes the data structure. More...

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

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

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

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

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

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

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

Public Member Functions inherited from ogdf::HeapBase< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >
	HeapBase (std::less< T > const &comp=std::less< T >())

virtual const std::less< T > &	comparator () const
	Returns the comparator used to sort the values in the heap. More...

virtual void	merge (BinaryHeap< T, std::less< T > > &other)
	Merges in values of `other` heap. More...

virtual const T &	top () const=0
	Returns the topmost value in the heap. More...

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. More...

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

int	higherArrayBound (int arraySize)

int	higherArraySize (int arraySize)

void	init (int initialSize)

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

int	lowerArrayBound (int arraySize)

int	lowerArraySize (int arraySize)

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

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

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

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

Private Attributes
int	m_arraySize

HeapEntry *	m_heapArray

int	m_initialSize

int	m_size

Additional Inherited Members
Public Types inherited from ogdf::HeapBase< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >
using	Handle = int *
	The type of handle used to identify stored values. More...

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 50 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 53 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 287 of file BinaryHeap.h.

◆ ~BinaryHeap()

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

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

inlinevirtual

Definition at line 65 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 172 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 112 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 306 of file BinaryHeap.h.

◆ decrease()

template<typename T , typename C >

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

overridevirtual

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

Implements ogdf::HeapBase< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >.

Definition at line 269 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 118 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 157 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 164 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 173 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 174 of file BinaryHeap.h.

◆ init()

template<typename T , typename C >

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

private

Definition at line 294 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 143 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 175 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 176 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 136 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< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >.

Definition at line 241 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< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >.

Definition at line 205 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 150 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 341 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 316 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 115 of file BinaryHeap.h.

◆ top()

template<typename T , typename C >

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

override

Returns the topmost value in the heap.

Returns: the topmost value

Definition at line 199 of file BinaryHeap.h.

◆ value()

template<typename T , typename C >

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

overridevirtual

Returns the value of that handle.

Parameters

handle The handle

Returns: The value

Implements ogdf::HeapBase< BinaryHeap< T, std::less< T > >, int, T, std::less< T > >.

Definition at line 278 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 191 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 185 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 194 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 188 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

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

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

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