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

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>

List of all members.

Public Types

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

Public Member Functions

 FibonacciHeap (int maxSize=0)
 The constructor of an empty Fibonacci heap.
 ~FibonacciHeap ()
 The destructor of a Fibonacci heap.
int Insert (const element &value)
 Inserts an element into the heap.
int Minimum () const
 Returns the number of the node that contains the minimum.
const element & Value (int number) const
 Returns the value of the node with the given number.
element ExtractMinimum ()
 Extracts the minimum from the heap.
void DecreaseKey (int number, const element &value)
 Decreases the key of the element identified by the given number to the new value.
void Delete (int number)
 Removes the element identified by the given number from the heap.

Static Public Attributes

static const int NullPtr = -1
 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 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 nodeCount
 The total number of nodes inserted to the heap and allocated in the multitable "nodes".
multitable< Nodenodes
 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< NodePtrauxArray
 An auto-expandable array used by the "Consolidate" procedure.
int 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.

Classes

struct  Node
 The structure that holds a graph node for the graph representation of a Fibonacci heap. More...


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 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  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 258 of file fibheap.h.

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

The destructor of a Fibonacci heap.

Definition at line 272 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 285 of file fibheap.h.


Member Function Documentation

template<class element>
int 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 300 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::minRoot, chomp::homology::FibonacciHeap< element >::minValue, chomp::homology::FibonacciHeap< element >::nodeCount, chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

template<class element>
int 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 343 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::minRoot.

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

Returns the value of the node with the given number.

Definition at line 349 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::nodes.

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 511 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::Consolidate(), chomp::homology::FibonacciHeap< element >::minRoot, chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

Referenced by chomp::homology::FibonacciHeap< element >::Delete().

template<class element>
void chomp::homology::FibonacciHeap< element >::DecreaseKey ( int  number,
const element &  value 
) [inline]

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

Definition at line 631 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::CascadingCut(), chomp::homology::FibonacciHeap< element >::Cut(), chomp::homology::FibonacciHeap< element >::minRoot, chomp::homology::FibonacciHeap< element >::minValue, chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

Referenced by chomp::homology::FibonacciHeap< element >::Delete().

template<class element>
void chomp::homology::FibonacciHeap< element >::Delete ( int  number  )  [inline]

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

Definition at line 664 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::ExtractMinimum(), and chomp::homology::FibonacciHeap< element >::minValue.

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

The assignment operator is not allowed.

Definition at line 293 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 392 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::arrayPrepared, chomp::homology::FibonacciHeap< element >::auxArray, chomp::homology::FibonacciHeap< element >::minRoot, chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

Referenced by chomp::homology::FibonacciHeap< element >::ExtractMinimum().

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 569 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::minRoot, chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

Referenced by chomp::homology::FibonacciHeap< element >::CascadingCut(), and chomp::homology::FibonacciHeap< element >::DecreaseKey().

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 608 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::Cut(), chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.

Referenced by chomp::homology::FibonacciHeap< element >::DecreaseKey().

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

Shows a graph starting at the given node using DFS.

Definition at line 228 of file fibheap.h.

References chomp::homology::FibonacciHeap< element >::nodes, and chomp::homology::FibonacciHeap< element >::NullPtr.


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>
const int chomp::homology::FibonacciHeap< element >::NullPtr = -1 [static]

The value used for a NULL pointer.

Definition at line 70 of file fibheap.h.

Referenced by chomp::homology::FibonacciHeap< element >::CascadingCut(), chomp::homology::FibonacciHeap< element >::Consolidate(), chomp::homology::FibonacciHeap< element >::Cut(), chomp::homology::FibonacciHeap< element >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::ExtractMinimum(), chomp::homology::FibonacciHeap< element >::Insert(), and chomp::homology::FibonacciHeap< element >::showGraph().

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.

Referenced by chomp::homology::FibonacciHeap< element >::Consolidate(), chomp::homology::FibonacciHeap< element >::Cut(), chomp::homology::FibonacciHeap< element >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::ExtractMinimum(), chomp::homology::FibonacciHeap< element >::Insert(), and chomp::homology::FibonacciHeap< element >::Minimum().

template<class element>
int 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.

Referenced by chomp::homology::FibonacciHeap< element >::Insert().

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.

Referenced by chomp::homology::FibonacciHeap< element >::CascadingCut(), chomp::homology::FibonacciHeap< element >::Consolidate(), chomp::homology::FibonacciHeap< element >::Cut(), chomp::homology::FibonacciHeap< element >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::ExtractMinimum(), chomp::homology::FibonacciHeap< element >::Insert(), chomp::homology::FibonacciHeap< element >::showGraph(), and chomp::homology::FibonacciHeap< element >::Value().

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.

Referenced by chomp::homology::FibonacciHeap< element >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::Delete(), and chomp::homology::FibonacciHeap< element >::Insert().

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.

Referenced by chomp::homology::FibonacciHeap< element >::Consolidate().

template<class element>
int chomp::homology::FibonacciHeap< element >::arrayPrepared [private]

The size of the prepared data in the array.

Definition at line 186 of file fibheap.h.

Referenced by chomp::homology::FibonacciHeap< element >::Consolidate().


The documentation for this class was generated from the following file:
Generated on Wed Nov 21 11:08:42 2007 for The Uniform Expansion Software by  doxygen 1.5.3