This template contains the definition of a Fibonacci heap that can be used as an efficient priority queue, for example, in the Dijxtra graph algorithm. More...

#include <chomp/struct/fibheap.h>

Classes
struct	Node
	The structure that holds a graph node for the graph representation of a Fibonacci heap. More...
Public Types
typedef int_t	NodePtr
	The type of a pointer to a node in the Fibonacci heap.
Public Member Functions
	FibonacciHeap (int_t maxSize=0)
	The constructor of an empty Fibonacci heap.
	~FibonacciHeap ()
	The destructor of a Fibonacci heap.
int_t	Insert (const element &value)
	Inserts an element into the heap.
int_t	Minimum () const
	Returns the number of the node that contains the minimum.
const element &	Value (int_t number) const
	Returns the value of the node with the given number.
element	ExtractMinimum ()
	Extracts the minimum from the heap.
void	DecreaseKey (int_t number, const element &value)
	Decreases the key of the element identified by the given number to the new value.
void	Delete (int_t number)
	Removes the element identified by the given number from the heap.
Static Public Attributes
static const int_t	NullPtr
	The value used for a NULL pointer.
Private Member Functions
	FibonacciHeap (const FibonacciHeap< element > &)
	The copy constructor is not allowed.
FibonacciHeap< element > &	operator= (const FibonacciHeap< element > &)
	The assignment operator is not allowed.
void	Consolidate ()
	Consolidates the Fibonacci heap by joining roots of equal degree.
void	Cut (const typename FibonacciHeap< element >::NodePtr &x, const typename FibonacciHeap< element >::NodePtr &y)
	Cuts the tree.
void	CascadingCut (typename FibonacciHeap< element >::NodePtr y)
	Does a cascading cut of the tree.
void	showGraph (std::ostream &out, int_t depth, const typename FibonacciHeap< element >::NodePtr &x) const
	Shows a graph starting at the given node using DFS.
Private Attributes
NodePtr	minRoot
	A pointer to the minimal element in the list of roots.
int_t	nodeCount
	The total number of nodes inserted to the heap and allocated in the multitable "nodes".
multitable< Node >	nodes
	The array of nodes which hold the elements inserted to the heap in this order.
element	minValue
	The minimal value that ever appeared in the heap.
multitable< NodePtr >	auxArray
	An auto-expandable array used by the "Consolidate" procedure.
int_t	arrayPrepared
	The size of the prepared data in the array.
Friends
std::ostream &	operator<< (std::ostream &out, const FibonacciHeap< element > &h)
	Operator << shows the heap to the output stream.

Detailed Description

template<class element>
class chomp::homology::FibonacciHeap< element >

This template contains the definition of a Fibonacci heap that can be used as an efficient priority queue, for example, in the Dijxtra graph algorithm.

Note that if the "Delete" function is used then the elements must support the arithmetic subtraction of 1 to create a value that is strictly smaller than the given one (like the integers). This is a very specialized implementation which does not support the "Union" operation. Moreover, the "Delete" or "ExtractMinimum" don't actually free the memory used by the deleted elements in this implementation. See the description of the functions in this class for more information.

Definition at line 63 of file fibheap.h.

Member Typedef Documentation

template<class element>

typedef int_t chomp::homology::FibonacciHeap< element >::NodePtr

The type of a pointer to a node in the Fibonacci heap.

Definition at line 67 of file fibheap.h.

Constructor & Destructor Documentation

template<class element >

chomp::homology::FibonacciHeap< element >::FibonacciHeap ( int_t maxSize = 0 ) [inline]

The constructor of an empty Fibonacci heap.

The maximal number of elements may be given if it is known.

Definition at line 261 of file fibheap.h.

template<class element >

chomp::homology::FibonacciHeap< element >::~FibonacciHeap ( ) [inline]

The destructor of a Fibonacci heap.

Definition at line 275 of file fibheap.h.

template<class element >

chomp::homology::FibonacciHeap< element >::FibonacciHeap ( const FibonacciHeap< element > & ) [inline, private]

The copy constructor is not allowed.

Definition at line 288 of file fibheap.h.

Member Function Documentation

template<class element >

void chomp::homology::FibonacciHeap< element >::CascadingCut ( typename FibonacciHeap< element >::NodePtr y ) [inline, private]

Does a cascading cut of the tree.

Definition at line 611 of file fibheap.h.

template<class element >

void chomp::homology::FibonacciHeap< element >::Consolidate ( ) [inline, private]

Consolidates the Fibonacci heap by joining roots of equal degree.

Definition at line 395 of file fibheap.h.

template<class element >

void chomp::homology::FibonacciHeap< element >::Cut	(	const typename FibonacciHeap< element >::NodePtr &	x,
		const typename FibonacciHeap< element >::NodePtr &	y
	)		`[inline, private]`

Cuts the tree.

Definition at line 572 of file fibheap.h.

template<class element >

void chomp::homology::FibonacciHeap< element >::DecreaseKey	(	int_t	number,
		const element &	value
	)		`[inline]`

Decreases the key of the element identified by the given number to the new value.

Definition at line 634 of file fibheap.h.

template<class element >

void chomp::homology::FibonacciHeap< element >::Delete ( int_t number ) [inline]

Removes the element identified by the given number from the heap.

Definition at line 667 of file fibheap.h.

template<class element >

element chomp::homology::FibonacciHeap< element >::ExtractMinimum ( ) [inline]

Extracts the minimum from the heap.

The element is removed from the heap and its value is returned.

Definition at line 514 of file fibheap.h.

template<class element >

int_t chomp::homology::FibonacciHeap< element >::Insert ( const element & value ) [inline]

Inserts an element into the heap.

Returns the number of the node which is to be used for decreasing the key or removing this element from the heap. The numbers are returned in the ascending order, starting at 0.

Definition at line 303 of file fibheap.h.

template<class element >

int_t chomp::homology::FibonacciHeap< element >::Minimum ( ) const [inline]

Returns the number of the node that contains the minimum.

This is the number given to the node at its insertion.

Definition at line 346 of file fibheap.h.

template<class element >

FibonacciHeap< element > & chomp::homology::FibonacciHeap< element >::operator= ( const FibonacciHeap< element > & ) [inline, private]

The assignment operator is not allowed.

Definition at line 296 of file fibheap.h.

template<class element >

void chomp::homology::FibonacciHeap< element >::showGraph	(	std::ostream &	out,
		int_t	depth,
		const typename FibonacciHeap< element >::NodePtr &	x
	)		const `[private]`

Shows a graph starting at the given node using DFS.

Definition at line 231 of file fibheap.h.

template<class element >

const element & chomp::homology::FibonacciHeap< element >::Value ( int_t number ) const [inline]

Returns the value of the node with the given number.

Definition at line 352 of file fibheap.h.

Friends And Related Function Documentation

template<class element>

std::ostream& operator<<	(	std::ostream &	out,
		const FibonacciHeap< element > &	h
	)		`[friend]`

Operator << shows the heap to the output stream.

Essentially, this might be useful for debugging purposes only.

Definition at line 202 of file fibheap.h.

Member Data Documentation

template<class element>

int_t chomp::homology::FibonacciHeap< element >::arrayPrepared [private]

The size of the prepared data in the array.

Definition at line 186 of file fibheap.h.

template<class element>

multitable<NodePtr> chomp::homology::FibonacciHeap< element >::auxArray [private]

An auto-expandable array used by the "Consolidate" procedure.

Definition at line 183 of file fibheap.h.

template<class element>

NodePtr chomp::homology::FibonacciHeap< element >::minRoot [private]

A pointer to the minimal element in the list of roots.

Definition at line 154 of file fibheap.h.

template<class element>

element chomp::homology::FibonacciHeap< element >::minValue [private]

The minimal value that ever appeared in the heap.

This value minus 1 is used as a substitute for the minus infinity while deleting elements from the heap with the use of the "Delete" function.

Definition at line 171 of file fibheap.h.

template<class element>

int_t chomp::homology::FibonacciHeap< element >::nodeCount [private]

The total number of nodes inserted to the heap and allocated in the multitable "nodes".

Definition at line 158 of file fibheap.h.

template<class element>

multitable<Node> chomp::homology::FibonacciHeap< element >::nodes [private]

The array of nodes which hold the elements inserted to the heap in this order.

The indices of these elements are returned while inserting them to the heap and can be used to access these nodes directly, e.g., in order to decrease their keys or delete them from the heap.

Definition at line 165 of file fibheap.h.

template<class element>

const int_t chomp::homology::FibonacciHeap< element >::NullPtr [static]

The value used for a NULL pointer.

Definition at line 70 of file fibheap.h.

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

chomp/struct/fibheap.h

chomp::homology::FibonacciHeap< element > Class Template Reference

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class element> class chomp::homology::FibonacciHeap< element >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class element>
class chomp::homology::FibonacciHeap< element >