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

Public Member Functions
	FibonacciHeap (int_t maxSize=0)
	The constructor of an empty Fibonacci heap. More...

	~FibonacciHeap ()
	The destructor of a Fibonacci heap. More...

int_t	Insert (const element &value)
	Inserts an element into the heap. More...

int_t	Minimum () const
	Returns the number of the node that contains the minimum. More...

const element &	Value (int_t number) const
	Returns the value of the node with the given number. More...

element	ExtractMinimum ()
	Extracts the minimum from the heap. More...

void	DecreaseKey (int_t number, const element &value)
	Decreases the key of the element identified by the given number to the new value. More...

void	Delete (int_t number)
	Removes the element identified by the given number from the heap. More...

Static Public Attributes
static const int_t	NullPtr
	The value used for a NULL pointer. More...

Private Member Functions
	FibonacciHeap (const FibonacciHeap< element > &)
	The copy constructor is not allowed. More...

FibonacciHeap< element > &	operator= (const FibonacciHeap< element > &)
	The assignment operator is not allowed. More...

void	Consolidate ()
	Consolidates the Fibonacci heap by joining roots of equal degree. More...

void	Cut (const typename FibonacciHeap< element >::NodePtr &x, const typename FibonacciHeap< element >::NodePtr &y)
	Cuts the tree. More...

void	CascadingCut (typename FibonacciHeap< element >::NodePtr y)
	Does a cascading cut of the tree. More...

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

Private Attributes
NodePtr	minRoot
	A pointer to the minimal element in the list of roots. More...

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

multitable< Node >	nodes
	The array of nodes which hold the elements inserted to the heap in this order. More...

element	minValue
	The minimal value that ever appeared in the heap. More...

multitable< NodePtr >	auxArray
	An auto-expandable array used by the "Consolidate" procedure. More...

int_t	arrayPrepared
	The size of the prepared data in the array. More...

Friends
std::ostream &	operator<< (std::ostream &out, const FibonacciHeap< element > &h)
	Operator << shows the heap to the output stream. 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 62 of file fibheap.h.

Member Typedef Documentation

◆ NodePtr

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

Constructor & Destructor Documentation

◆ FibonacciHeap() [1/2]

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 260 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 */

◆ ~FibonacciHeap()

template<class element >

chomp::homology::FibonacciHeap< element >::~FibonacciHeap

inline

The destructor of a Fibonacci heap.

Definition at line 274 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 */

◆ FibonacciHeap() [2/2]

template<class element >

chomp::homology::FibonacciHeap< element >::FibonacciHeap ( const FibonacciHeap< element > & )

inlineprivate

The copy constructor is not allowed.

Definition at line 287 of file fibheap.h.

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

Member Function Documentation

◆ CascadingCut()

template<class element >

void chomp::homology::FibonacciHeap< element >::CascadingCut ( typename FibonacciHeap< element >::NodePtr y )

inlineprivate

Does a cascading cut of the tree.

Definition at line 609 of file fibheap.h.

{
        // 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 */

◆ Consolidate()

template<class element >

void chomp::homology::FibonacciHeap< element >::Consolidate

inlineprivate

Consolidates the Fibonacci heap by joining roots of equal degree.

Definition at line 394 of file fibheap.h.

{
        // 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 */

◆ Cut()

template<class element >

void chomp::homology::FibonacciHeap< element >::Cut	(	const typename FibonacciHeap< element >::NodePtr &	x,
		const typename FibonacciHeap< element >::NodePtr &	y
	)

inlineprivate

Cuts the tree.

Definition at line 570 of file fibheap.h.

{
        // 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 */

◆ DecreaseKey()

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

{
        // 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 */

◆ Delete()

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

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

◆ ExtractMinimum()

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

{
        // 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 */

◆ Insert()

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

{
        // 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 */

◆ Minimum()

template<class element >

int_t chomp::homology::FibonacciHeap< element >::Minimum

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

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

◆ operator=()

template<class element >

FibonacciHeap< element > & chomp::homology::FibonacciHeap< element >::operator= ( const FibonacciHeap< element > & )

inlineprivate

The assignment operator is not allowed.

Definition at line 294 of file fibheap.h.

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

◆ showGraph()

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

{
        // 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 */

◆ Value()

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

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

Friends And Related Function Documentation

◆ operator<<

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

◆ arrayPrepared

template<class element >

int_t chomp::homology::FibonacciHeap< element >::arrayPrepared

private

The size of the prepared data in the array.

Definition at line 185 of file fibheap.h.

◆ auxArray

template<class element >

multitable<NodePtr> chomp::homology::FibonacciHeap< element >::auxArray

private

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

Definition at line 182 of file fibheap.h.

◆ minRoot

template<class element >

NodePtr chomp::homology::FibonacciHeap< element >::minRoot

private

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

Definition at line 153 of file fibheap.h.

◆ minValue

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

◆ nodeCount

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

◆ nodes

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

◆ NullPtr

template<class element >

const int_t chomp::homology::FibonacciHeap< element >::NullPtr

static

The value used for a NULL pointer.

Definition at line 69 of file fibheap.h.

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

chomp/struct/fibheap.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ NodePtr

Constructor & Destructor Documentation

◆ FibonacciHeap() [1/2]

◆ ~FibonacciHeap()

◆ FibonacciHeap() [2/2]

Member Function Documentation

◆ CascadingCut()

◆ Consolidate()

◆ Cut()

◆ DecreaseKey()

◆ Delete()

◆ ExtractMinimum()

◆ Insert()

◆ Minimum()

◆ operator=()

◆ showGraph()

◆ Value()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ arrayPrepared

◆ auxArray

◆ minRoot

◆ minValue

◆ nodeCount

◆ nodes

◆ NullPtr