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.

Additional Inherited Members
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 89 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

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

Definition at line 185 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 191 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 294 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 252 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 338 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 324 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 262 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 346 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 230 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 218 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 196 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 278 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 363 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 354 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 212 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 153 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 159 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 157 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 162 of file FibonacciHeap.h.

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

include/ogdf/basic/heap/FibonacciHeap.h

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_type

Constructor & Destructor Documentation

◆ FibonacciHeap()

◆ ~FibonacciHeap()

Member Function Documentation

◆ compress()

◆ decrease()

◆ detach()

◆ link()

◆ merge() [1/2]

◆ merge() [2/2]

◆ pop()

◆ push()

◆ release()

◆ remove()

◆ restore()

◆ splice()

◆ top()

◆ value()

Member Data Documentation

◆ m_knot

◆ m_minimal

◆ m_ranked

Open
Graph Drawing
Framework