 # OpenGraph DrawingFramework

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

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

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

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

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

Definition at line 154 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 162 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 160 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 165 of file FibonacciHeap.h.

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