#include <chomp/struct/fibheap.h>
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< 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 | 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... |
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.
typedef int chomp::homology::FibonacciHeap< element >::NodePtr |
chomp::homology::FibonacciHeap< element >::FibonacciHeap | ( | int | maxSize = 0 |
) | [inline] |
chomp::homology::FibonacciHeap< element >::~FibonacciHeap | ( | ) | [inline] |
chomp::homology::FibonacciHeap< element >::FibonacciHeap | ( | const FibonacciHeap< element > & | ) | [inline, private] |
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.
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.
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.
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().
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().
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.
FibonacciHeap< element > & chomp::homology::FibonacciHeap< element >::operator= | ( | const FibonacciHeap< element > & | ) | [inline, private] |
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().
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().
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().
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.
std::ostream& operator<< | ( | std::ostream & | out, | |
const FibonacciHeap< element > & | h | |||
) | [friend] |
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().
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().
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().
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().
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().
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().
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().