OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

virtual ~FibonacciHeap ()
Destructs the heap.

void decrease (FibonacciHeapNode< T > *heapNode, const T &value) override
Decreases value of the given heapNode to value.

void merge (FibonacciHeap< T, C > &other) override
Merges in values of other heap.

void pop () override
Removes the top element from the heap.

FibonacciHeapNode< T > * push (const T &value) override
Inserts a new node with given value into a heap.

const T & top () const override
Returns reference to the top element in the heap.

const T & value (FibonacciHeapNode< T > *heapNode) const override
Returns the value of the node.

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

void detach (FibonacciHeapNode< T > *heapNode)
Detaches given heapNode from its list and makes it self-circulate.

void link (FibonacciHeapNode< T > *root, FibonacciHeapNode< T > *child)
Makes child node a child of root node.

void merge (FibonacciHeapNode< T > *other)
Merges other list into current heap list.

void release (FibonacciHeapNode< T > *heapNode)
Recursively releases memory starting at heapNode.

void remove ()
Removes minimal tree and moves its children to tree list.

void restore (FibonacciHeapNode< T > *heapNode)
Restores heap ordering in heapNode by making (cascade) cut.

void splice (FibonacciHeapNode< T > *target, FibonacciHeapNode< T > *heapNode)
Moves heapNode from its list to the target list.

Private Attributes

FibonacciHeapNode< T > * m_knot
Used for efficient tree list manipulation.

FibonacciHeapNode< T > * m_minimal
Handle to the tree with lowest root priority.

std::array< FibonacciHeapNode< T > *, sizeof(size_t) *8 > m_ranked
Used to compress trees.

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::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
 T Denotes value type of inserted elements. C Denotes comparison functor determining value ordering.

Definition at line 87 of file FibonacciHeap.h.

◆ base_type

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

Definition at line 88 of file FibonacciHeap.h.

◆ FibonacciHeap()

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

Creates empty Fibonacci heap.

Parameters
 cmp Comparison functor determining value ordering. initialSize ignored by this implementation.

Definition at line 183 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 189 of file FibonacciHeap.h.

◆ 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 292 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
 heapNode A node for which the value is to be decreased. value A new value for the node.

Definition at line 250 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 336 of file FibonacciHeap.h.

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 322 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
 other A heap to be merged in.

Definition at line 260 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 344 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< IMPL, H, T, C >.

Definition at line 228 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
 value A value to be inserted.
Returns
Handle to the inserted node.

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

Definition at line 216 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 194 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 276 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 361 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 352 of file FibonacciHeap.h.

◆ top()

template<typename T , typename C >
 const T & ogdf::FibonacciHeap< T, C >::top ( ) const
inlineoverridevirtual

Returns reference to the top element in the heap.

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

Definition at line 210 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
 heapNode The nodes handle
Returns
the value of the node

Definition at line 151 of file FibonacciHeap.h.

◆ m_knot

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

Used for efficient tree list manipulation.

Definition at line 157 of file FibonacciHeap.h.

◆ m_minimal

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

Handle to the tree with lowest root priority.

Definition at line 155 of file FibonacciHeap.h.

◆ m_ranked

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

Used to compress trees.

Definition at line 160 of file FibonacciHeap.h.

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