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 <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.

                                                          :
        minRoot (NullPtr), nodeCount (0), nodes (maxSize), arrayPrepared (0)
{
        // allocate a new pool for elements if this is the first heap
//      if (!heapsInUse)
//              p = new pool<typename FibonacciHeap<element>::Node>;

        // increase the number of heaps in use
//      ++ heapsInUse;

        return;
} /* FibonacciHeap::FibonacciHeap */

template<class element >

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

The destructor of a Fibonacci heap.

Definition at line 275 of file fibheap.h.

{
        // decrease the number of heaps in use
//      -- heapsInUse;

        // delete the pool for elements if this was the last heap
//      if (!heapsInUse)
//              delete p;

        return;
} /* FibonacciHeap::~FibonacciHeap */

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.

{
        throw "Copy constructor for a Fibonacci heap not implemented.";
        return;
} /* FibonacciHeap::FibonacciHeap */

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.

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

{
        // do the cascading cut while the node has a parent
        while (!(nodes [y]. parent == NullPtr))
        {
                // if this is the first time the node lost its child,
                // then just mark the node and exit the cascading cut
                if (!nodes [y]. mark)
                {
                        nodes [y]. mark = true;
                        return;
                }

                // cut the node and continue the cascading cut
                // with its parent
                NodePtr z = nodes [y]. parent;
                Cut (y, z);
                y = z;
        }
        return;
} /* FibonacciHeap::CascadingCut */

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.

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().

{
        // do nothing if the heap is empty
        if (minRoot == NullPtr)
                return;

        // for each node in the root list of the heap...
        NodePtr node = minRoot;
        int_t maxDegree = 0;
        do
        {
                // take the node for the loop and get its degree
                NodePtr x = node;
                int_t d = nodes [x]. degree;

                // prepare the next node from the root list for the next time
                node = nodes [node]. right;

                // expand the auxiliary array if necessary
                while (arrayPrepared <= d)
                        auxArray [arrayPrepared ++] = NullPtr;

                // update the strict upper limit on the degree used
                if (maxDegree <= d)
                        maxDegree = d + 1;

                // join this tree with another one of the same degree if any
                while (auxArray [d] != NullPtr)
                {
                        // take the node of the same degree as x
                        NodePtr y = auxArray [d];

                        // swap the node pointers if necessary
                        if (nodes [y]. key < nodes [x]. key)
                        {
                                NodePtr tmp = x;
                                x = y;
                                y = tmp;
                        }

                        // clear the mark of the node y
                        nodes [y]. mark = false;

                        // make the node y a child of the node x
                        nodes [y]. parent = x;
                        NodePtr child = nodes [x]. child;
                        if (child == NullPtr)
                        {
                                nodes [x]. child = y;
                                nodes [y]. left = y;
                                nodes [y]. right = y;
                        }
                        else
                        {
                                nodes [y]. left = child;
                                nodes [y]. right = nodes [child]. right;
                                nodes [child]. right = y;
                                nodes [nodes [y]. right]. left = y;
                        }
                        ++ nodes [x]. degree;

                        // clear the entry which stored the node of degree d
                        auxArray [d] = NullPtr;

                        // increase the degree to the degree of x
                        ++ d;

                        // expand the auxiliary array if necessary
                        if (arrayPrepared <= d)
                                auxArray [arrayPrepared ++] = NullPtr;

                        // update the strict upper limit on the degree used
                        if (maxDegree <= d)
                                maxDegree = d + 1;
                }

                // put this node in the array
                auxArray [d] = x;

        } while (node != minRoot);

        // reconstruct the root list from the auxiliary array
        minRoot = NullPtr;
        for (int_t d = 0; d < maxDegree; ++ d)
        {
                // skip entries of the array which don't point to nodes
                if (auxArray [d] == NullPtr)
                        continue;

                // take the node pointer of the array
                NodePtr nodePtr = auxArray [d];
                auxArray [d] = NullPtr;
                Node &node = nodes [nodePtr];

                // link this node to the root list
                if (minRoot == NullPtr)
                {
                        node. left = nodePtr;
                        node. right = nodePtr;
                }
                else
                {
                        node. left = minRoot;
                        node. right = nodes [minRoot]. right;
                        nodes [node. left]. right = nodePtr;
                        nodes [node. right]. left = nodePtr;
                }

                // update the pointer to the minimal root node if necessary
                if ((minRoot == NullPtr) ||
                        (node. key < nodes [minRoot]. key))
                {
                        minRoot = nodePtr;
                }
        }
        return;
} /* FibonacciHeap::Consolidate */

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.

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

{
        // remove x from the children of y:
        // case 1: if x is the only child of y
        nodes [x]. parent = NullPtr;
        if (nodes [x]. right == x)
        {
                nodes [y]. child = NullPtr;
        }
        //case 2: if there are also other children of y
        else
        {
                NodePtr leftChild = nodes [x]. left;
                NodePtr rightChild = nodes [x]. right;
                nodes [y]. child = rightChild;
                nodes [leftChild]. right = rightChild;
                nodes [rightChild]. left = leftChild;
        }

        // update the degree of y
        -- nodes [y]. degree;

        // add x to the root list of the heap
        NodePtr leftRoot = minRoot;
        NodePtr rightRoot = nodes [minRoot]. right;
        nodes [x]. left = leftRoot;
        nodes [x]. right = rightRoot;
        nodes [leftRoot]. right = x;
        nodes [rightRoot]. left = x;

        // clear the marking of the node x if any
        nodes [x]. mark = false;

        return;
} /* FibonacciHeap::Cut */

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.

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().

{
        // translate the number to a node pointer
        NodePtr x (number);

        // ignore this action if the node is no longer in the heap
        if (nodes [x]. degree == -1)
                return;

        // update the minimal value in the heap
        if (value < minValue)
                minValue = value;

        // update the value of the node
        nodes [x]. key = value;

        // cut the tree so that the node x is in the root list
        NodePtr y = nodes [x]. parent;
        if ((y != NullPtr) && (value < nodes [y]. key))
        {
                Cut (x, y);
                CascadingCut (y);
        }

        // update the pointer to the minimal node in the root list
        if (value < nodes [minRoot]. key)
                minRoot = x;

        return;
} /* FibonacciHeap::DecreaseKey */

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.

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

{
        element value = minValue;
        DecreaseKey (number, value - 1);
        ExtractMinimum ();
        minValue = value;
        return;
} /* FibonacciHeap::Delete */

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.

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().

{
        // determine the node with the minimum to extract
        NodePtr nodePtr = minRoot;
        Node &node = nodes [minRoot];

        // make the children of the node become root nodes
        // and attach them to the root list
        NodePtr child = node. child;
        if (child != NullPtr)
        {
                // clear the child pointer in the parent
                node. child = NullPtr;

                // clear the parent pointers in the children
                while (nodes [child]. parent != NullPtr)
                {
                        nodes [child]. parent = NullPtr;
                        child = nodes [child]. right;
                }

                // attach the children to the root list
                NodePtr leftChild = child;
                NodePtr rightChild = nodes [child]. right;
                NodePtr leftRoot = nodePtr;
                NodePtr rightRoot = node. right;
                nodes [leftRoot]. right = rightChild;
                nodes [rightRoot]. left = leftChild;
                nodes [leftChild]. right = rightRoot;
                nodes [rightChild]. left = leftRoot;
        }

        // make the min root pointer point at any other node
        // and remove the node from the root list
        if (node. right != nodePtr)
        {
                minRoot = node. right;
                nodes [minRoot]. left = node. left;
                nodes [node. left]. right = minRoot;
        }
        else
                minRoot = NullPtr;

        // reset the fields in the node to avoid any confusion in the future
        node. left = NullPtr;
        node. right = NullPtr;
        node. parent = NullPtr;
        node. child = NullPtr;
        node. degree = -1;

        // consolidate the heap
        Consolidate ();

        return node. key;
} /* FibonacciHeap::ExtractMinimum */

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.

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.

{
        // allocate memory for the new node
        NodePtr nodePtr = nodeCount;

        // update the minimal value
        if (!nodeCount)
                minValue = value;
        else if (value < minValue)
                minValue = value;

        // fill in the fields of the new node
        Node &node = nodes [nodePtr];
        node. key = value;
        node. mark = false;
        node. degree = 0;
        node. number = nodeCount;
        node. parent = NullPtr;
        node. child = NullPtr;

        // insert the node to the unordered bidirectional list of roots
        if (minRoot == NullPtr)
        {
                node. left = nodePtr;
                node. right = nodePtr;
        }
        else
        {
                node. left = nodes [minRoot]. left;
                node. right = minRoot;
                nodes [node. left]. right = nodePtr;
                nodes [node. right]. left = nodePtr;
        }

        // make a correction to the pointer to the minimal root if necessary
        if ((minRoot == NullPtr) || (value < nodes [minRoot]. key))
                minRoot = nodePtr;

        // return the number of the new node and increase the number of nodes
        return nodeCount ++;
} /* FibonacciHeap::Insert */

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.

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

{
        return minRoot;
} /* FibonacciHeap::Minimum */

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.

{
        throw "Assignment operator for a Fibonacci heap not implemented.";
        return *this;
} /* FibonacciHeap::operator = */

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.

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

{
        // show this node
        for (int_t i = 0; i < depth; ++ i)
                out << "|   ";
        out << "+-- [" << nodes [x]. number << ": " << nodes [x]. key << "]";
        if (nodes [x]. left != NullPtr)
                out << " left=" << nodes [x]. left;
        if (nodes [x]. right != NullPtr)
                out << " right=" << nodes [x]. right;
        if (nodes [x]. parent != NullPtr)
                out << " parent=" << nodes [x]. parent;
        if (nodes [x]. child != NullPtr)
                out << " child=" << nodes [x]. child;
        out << " deg=" << nodes [x]. degree << "\n";

        // show all the children trees
        NodePtr child = nodes [x]. child;
        if (child == NullPtr)
                return;
        do
        {
                showGraph (out, depth + 1, child);
                child = nodes [child]. right;
        } while (child != nodes [x]. child);
        return;
} /* FibonacciHeap::showGraph */

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.

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

{
        return nodes [number]. key;
} /* FibonacciHeap::Value */

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.

        {
                out << "Fibonacci heap (min root = " << h. minRoot << "):\n";
                NodePtr rootPtr = h. minRoot;
                if (rootPtr == NullPtr)
                        return out;
                do
                {
                        h. showGraph (out, 0, rootPtr);
                        rootPtr = h. nodes [rootPtr]. right;
                } while (rootPtr != h. minRoot);
                return out;
        } /* operator << */

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.

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

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>

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 >::DecreaseKey(), chomp::homology::FibonacciHeap< element >::ExtractMinimum(), chomp::homology::FibonacciHeap< element >::Insert(), and chomp::homology::FibonacciHeap< element >::Minimum().

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>

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.

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 >::Consolidate(), 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>

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

The value used for a NULL pointer.

Definition at line 70 of file fibheap.h.

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

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