Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::BinaryHeap< T, C > Class Template Reference

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
 
HeapEntrym_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
TDenotes value type of inserted elements.
CDenotes 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
compComparison functor determining value ordering.
initialSizeThe 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
handleThe handle of the value to be decreased
valueThe 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
valueThe 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
handleThe 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: