Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

Fibonacci heap implementation. More...

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

+ Inheritance diagram for ogdf::FibonacciHeap< T, C >:

Public Member Functions

 FibonacciHeap (const C &cmp=C(), int initialSize=-1)
 Creates empty Fibonacci heap. More...
 
virtual ~FibonacciHeap ()
 Destructs the heap. More...
 
void decrease (FibonacciHeapNode< T > *heapNode, const T &value) override
 Decreases value of the given heapNode to value. More...
 
void merge (FibonacciHeap< T, C > &other) override
 Merges in values of other heap. More...
 
void pop () override
 Removes the top element from the heap. More...
 
FibonacciHeapNode< T > * push (const T &value) override
 Inserts a new node with given value into a heap. More...
 
const T & top () const override
 Returns reference to the top element in the heap. More...
 
const T & value (FibonacciHeapNode< T > *heapNode) const override
 Returns the value of the node. More...
 
- Public Member Functions inherited from ogdf::HeapBase< FibonacciHeap< T, std::less< T > >, FibonacciHeapNode< T >, 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 decrease (Handle handle, const T &value)=0
 Decreases a single value. More...
 
virtual void merge (FibonacciHeap< 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...
 
virtual const T & value (const Handle handle) const=0
 Returns the value of that handle. More...
 

Private Types

using base_type = HeapBase< FibonacciHeap< T, C >, FibonacciHeapNode< T >, T, C >
 

Private Member Functions

void compress ()
 Reduces number of trees inside a heap by linking ones with same degree. More...
 
void detach (FibonacciHeapNode< T > *heapNode)
 Detaches given heapNode from its list and makes it self-circulate. More...
 
void link (FibonacciHeapNode< T > *root, FibonacciHeapNode< T > *child)
 Makes child node a child of root node. More...
 
void merge (FibonacciHeapNode< T > *other)
 Merges other list into current heap list. More...
 
void release (FibonacciHeapNode< T > *heapNode)
 Recursively releases memory starting at heapNode. More...
 
void remove ()
 Removes minimal tree and moves its children to tree list. More...
 
void restore (FibonacciHeapNode< T > *heapNode)
 Restores heap ordering in heapNode by making (cascade) cut. More...
 
void splice (FibonacciHeapNode< T > *target, FibonacciHeapNode< T > *heapNode)
 Moves heapNode from its list to the target list. More...
 

Private Attributes

FibonacciHeapNode< T > * m_knot
 Used for efficient tree list manipulation. More...
 
FibonacciHeapNode< T > * m_minimal
 Handle to the tree with lowest root priority. More...
 
std::array< FibonacciHeapNode< T > *, sizeof(size_t) *8 > m_ranked
 Used to compress trees. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::HeapBase< FibonacciHeap< T, std::less< T > >, FibonacciHeapNode< T >, T, std::less< T > >
using Handle = FibonacciHeapNode< T > *
 The type of handle used to identify stored values. More...
 

Detailed Description

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

Fibonacci heap implementation.

This implementation is based on Wikipedia article, original paper by Fredman and Tarjan and borrows some ideas from: http://www.cs.princeton.edu/~wayne/cs423/fibonacci/FibonacciHeapAlgorithm.html

Template Parameters
TDenotes value type of inserted elements.
CDenotes comparison functor determining value ordering.

Definition at line 87 of file FibonacciHeap.h.

Member Typedef Documentation

◆ base_type

template<typename T , typename C = std::less<T>>
using ogdf::FibonacciHeap< T, C >::base_type = HeapBase<FibonacciHeap<T, C>, FibonacciHeapNode<T>, T, C>
private

Definition at line 90 of file FibonacciHeap.h.

Constructor & Destructor Documentation

◆ FibonacciHeap()

template<typename T , typename C >
ogdf::FibonacciHeap< T, C >::FibonacciHeap ( const C &  cmp = C(),
int  initialSize = -1 
)
explicit

Creates empty Fibonacci heap.

Parameters
cmpComparison functor determining value ordering.
initialSizeignored by this implementation.

Definition at line 189 of file FibonacciHeap.h.

◆ ~FibonacciHeap()

template<typename T , typename C >
ogdf::FibonacciHeap< T, C >::~FibonacciHeap
virtual

Destructs the heap.

If the heap is not empty, destructors of contained elements are called and used storage is deallocated.

Definition at line 197 of file FibonacciHeap.h.

Member Function Documentation

◆ compress()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::compress
inlineprivate

Reduces number of trees inside a heap by linking ones with same degree.

Definition at line 318 of file FibonacciHeap.h.

◆ decrease()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::decrease ( FibonacciHeapNode< T > *  heapNode,
const T &  value 
)
override

Decreases value of the given heapNode to value.

Behaviour of this function is undefined if node does not belong to a the heap or new value is greater than old one.

Parameters
heapNodeA node for which the value is to be decreased.
valueA new value for the node.

Definition at line 270 of file FibonacciHeap.h.

◆ detach()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::detach ( FibonacciHeapNode< T > *  heapNode)
inlineprivate

Detaches given heapNode from its list and makes it self-circulate.

Definition at line 367 of file FibonacciHeap.h.

◆ link()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::link ( FibonacciHeapNode< T > *  root,
FibonacciHeapNode< T > *  child 
)
inlineprivate

Makes child node a child of root node.

Definition at line 350 of file FibonacciHeap.h.

◆ merge() [1/2]

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::merge ( FibonacciHeap< T, C > &  other)
override

Merges in values of other heap.

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

Parameters
otherA heap to be merged in.

Definition at line 282 of file FibonacciHeap.h.

◆ merge() [2/2]

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::merge ( FibonacciHeapNode< T > *  other)
inlineprivate

Merges other list into current heap list.

Definition at line 377 of file FibonacciHeap.h.

◆ pop()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::pop
overridevirtual

Removes the top element from the heap.

Behaviour of this function is undefined if the heap is empty.

Implements ogdf::HeapBase< FibonacciHeap< T, std::less< T > >, FibonacciHeapNode< T >, T, std::less< T > >.

Definition at line 244 of file FibonacciHeap.h.

◆ push()

template<typename T , typename C >
FibonacciHeapNode< T > * ogdf::FibonacciHeap< T, C >::push ( const T &  value)
overridevirtual

Inserts a new node with given value into a heap.

Parameters
valueA value to be inserted.
Returns
Handle to the inserted node.

Implements ogdf::HeapBase< FibonacciHeap< T, std::less< T > >, FibonacciHeapNode< T >, T, std::less< T > >.

Definition at line 230 of file FibonacciHeap.h.

◆ release()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::release ( FibonacciHeapNode< T > *  heapNode)
private

Recursively releases memory starting at heapNode.

Definition at line 204 of file FibonacciHeap.h.

◆ remove()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::remove
inlineprivate

Removes minimal tree and moves its children to tree list.

Definition at line 300 of file FibonacciHeap.h.

◆ restore()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::restore ( FibonacciHeapNode< T > *  heapNode)
inlineprivate

Restores heap ordering in heapNode by making (cascade) cut.

Definition at line 399 of file FibonacciHeap.h.

◆ splice()

template<typename T , typename C >
void ogdf::FibonacciHeap< T, C >::splice ( FibonacciHeapNode< T > *  target,
FibonacciHeapNode< T > *  heapNode 
)
inlineprivate

Moves heapNode from its list to the target list.

Definition at line 387 of file FibonacciHeap.h.

◆ top()

template<typename T , typename C >
const T & ogdf::FibonacciHeap< T, C >::top
inlineoverride

Returns reference to the top element in the heap.

Definition at line 222 of file FibonacciHeap.h.

◆ value()

template<typename T , typename C = std::less<T>>
const T& ogdf::FibonacciHeap< T, C >::value ( FibonacciHeapNode< T > *  heapNode) const
inlineoverride

Returns the value of the node.

Parameters
heapNodeThe nodes handle
Returns
the value of the node

Definition at line 154 of file FibonacciHeap.h.

Member Data Documentation

◆ m_knot

template<typename T , typename C = std::less<T>>
FibonacciHeapNode<T>* ogdf::FibonacciHeap< T, C >::m_knot
private

Used for efficient tree list manipulation.

Definition at line 162 of file FibonacciHeap.h.

◆ m_minimal

template<typename T , typename C = std::less<T>>
FibonacciHeapNode<T>* ogdf::FibonacciHeap< T, C >::m_minimal
private

Handle to the tree with lowest root priority.

Definition at line 160 of file FibonacciHeap.h.

◆ m_ranked

template<typename T , typename C = std::less<T>>
std::array<FibonacciHeapNode<T> *, sizeof(size_t) * 8> ogdf::FibonacciHeap< T, C >::m_ranked
private

Used to compress trees.

Definition at line 165 of file FibonacciHeap.h.


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