FibonacciHeap< Data, Key > Class Template Reference

Template class for a Fibonacci Heap data structure. More...

#include <FiboHeap.hpp>

Public Member Functions
	FibonacciHeap ()
	Constructor. More...
	~FibonacciHeap ()
	Destructor. More...
bool	empty () const
	Check if the heap is empty. More...
PNode	minimum () const
	Return the node associated with the minimum key. More...
void	printRoots (ostream &out) const
	Print the roots in an output stream. More...
void	merge (const FibonacciHeap &other)
	Fibonacci-Heap union procedure. More...
PNode	insert (Data d, Key k)
	Insert a node to the heap. More...
void	deletemin ()
	Remove the minimum node of the heap, i.e. the Fibonacci Heap Extract Min procedure. More...
void	decreaseKey (PNode node, Key newKey)
	Decrease the key of a node to a given value. More...
void	remove (PNode node, Key minusInfinity)
	Remove a node from the heap. More...

Protected Member Functions
PNode	insertNode (PNode newNode)
	Insert a node to the heap. More...

Private Types
typedef FibonacciHeapNode < Data, Key > *	PNode

Private Attributes
PNode	rootWithMinKey
	a circular d-list of nodes More...
uint	count
	total number of elements in heap More...
uint	maxDegree
	maximum degree (=child count) of a root in the circular d-list More...

Detailed Description

template<typename Data, typename Key>
class FibonacciHeap< Data, Key >

Template class for a Fibonacci Heap data structure.

This class implements a Fibonacci heap data structure which is a min-heap of Fibonacci Nodes sorted by Key

See http://en.wikipedia.org/wiki/Fibonacci_heap and http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html for references.

Member Typedef Documentation

template<typename Data , typename Key >

typedef FibonacciHeapNode<Data,Key>* FibonacciHeap< Data, Key >::PNode

private

Constructor & Destructor Documentation

template<typename Data , typename Key >

FibonacciHeap< Data, Key >::FibonacciHeap ( )

inline

Constructor.

template<typename Data , typename Key >

FibonacciHeap< Data, Key >::~FibonacciHeap ( )

inline

Destructor.

Member Function Documentation

template<typename Data , typename Key >

void FibonacciHeap< Data, Key >::decreaseKey ( PNode  node, Key  newKey  )

inline

Decrease the key of a node to a given value.

Parameters

node	a node of which key is to be decreased
newKey	the new key given to the node

template<typename Data , typename Key >

void FibonacciHeap< Data, Key >::deletemin ( )

inline

Remove the minimum node of the heap, i.e. the Fibonacci Heap Extract Min procedure.

Phase 1: Make all the removed root's children new roots:

Phase 2-a: handle the case where we delete the last myKey:

Phase 2: merge roots with the same degree:

Phase 3: remove the current root, and calculate the new rootWithMinKey:

template<typename Data , typename Key >

bool FibonacciHeap< Data, Key >::empty ( ) const

inline

Check if the heap is empty.

Returns

true if heap is empty, false otherwise

template<typename Data , typename Key >

PNode FibonacciHeap< Data, Key >::insert ( Data  d, Key  k  )

inline

Insert a node to the heap.

Parameters

d	data of the node to be added to the heap
k	value of the node to be added to the heap

Returns

a pointer to the newly added node

template<typename Data , typename Key >

PNode FibonacciHeap< Data, Key >::insertNode ( PNode  newNode )

inlineprotected

Insert a node to the heap.

Parameters

newNode

a pointer to the node to be added to the heap

Returns

a pointer to the newly added node

template<typename Data , typename Key >

void FibonacciHeap< Data, Key >::merge ( const FibonacciHeap< Data, Key > &  other )

inline

Fibonacci-Heap union procedure.

Merge a Fibonnacci heap with the current one.

Parameters

other

a second Fibonnacci heap to merge with the heap

template<typename Data , typename Key >

PNode FibonacciHeap< Data, Key >::minimum ( ) const

inline

Return the node associated with the minimum key.

Returns

the minimum Fibonnaci node of the heap

template<typename Data , typename Key >

void FibonacciHeap< Data, Key >::printRoots ( ostream &  out ) const

inline

Print the roots in an output stream.

Parameters

out	an output stream

template<typename Data , typename Key >

void FibonacciHeap< Data, Key >::remove ( PNode  node, Key  minusInfinity  )

inline

Remove a node from the heap.

Parameters

node	the node to remove from the heap
minusInfinity	a key lower to every other key in the heap

Member Data Documentation

template<typename Data , typename Key >

uint FibonacciHeap< Data, Key >::count

private

total number of elements in heap

template<typename Data , typename Key >

uint FibonacciHeap< Data, Key >::maxDegree

private

maximum degree (=child count) of a root in the circular d-list

template<typename Data , typename Key >

PNode FibonacciHeap< Data, Key >::rootWithMinKey

private

a circular d-list of nodes

---

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

• /home/johan/Documents/UNamur/VirtualBelgium/Workspace/VirtualBelgium/include/FiboHeap.hpp