Fibonacci heap. More...

#include <fibonacci_heap.hh>

Inheritance diagram for mln::util::fibonacci_heap< P, T >:

Public Types
typedef Object< void >	category
typedef T	element
typedef fibonacci_heap< P, T >	exact_t
Public Member Functions
void	clear ()
	Clear all elements in the heap and make the heap empty.
	fibonacci_heap ()
	Default constructor.
	fibonacci_heap (const fibonacci_heap< P, T > &node)
	Copy constructor Be ware that once this heap is constructed, the argument `node` is cleared and all its elements are part of this new heap.
const T &	front () const
	Return the minimum value in the heap.
bool	is_empty () const
	Is it empty?
bool	is_valid () const
	return false if it is empty.
unsigned	nelements () const
	Return the number of elements.
fibonacci_heap< P, T > &	operator= (fibonacci_heap< P, T > &rhs)
	Assignment operator.
T	pop_front ()
	Return and remove the minimum value in the heap.
std::ostream &	print_ (std::ostream &ostr, internal::fibonacci_heap_node< P, T > tree=0, internal::fibonacci_heap_node< P, T > parent=0) const
void	push (fibonacci_heap< P, T > &other_heap)
	Take `other_heap's` elements and insert them in this heap.
void	push (const P &priority, const T &value)
	Push a new element in the heap.
	~fibonacci_heap ()
Private Member Functions
void	add_to_root_list (internal::fibonacci_heap_node< P, T > *)
void	cascading_cut (internal::fibonacci_heap_node< P, T > *)
	Cuts each node in parent list, putting successive ancestor nodes on the root list until we either arrive at the root list or until we find an ancestor that is unmarked.
void	consolidate ()
	Internal function that reorganizes heap as part of an pop_front().
void	cut (internal::fibonacci_heap_node< P, T > lhs, internal::fibonacci_heap_node< P, T > rhs)
	Remove node `lhs` from the child list of its parent node `rhs`.
int	decrease_key (internal::fibonacci_heap_node< P, T > *node, internal::fibonacci_heap_node< P, T > &key)
	Allow to change a node value.
void	exchange (internal::fibonacci_heap_node< P, T > &lhs, internal::fibonacci_heap_node< P, T > &rhs)
	Swap the two given nodes.
void	insert (internal::fibonacci_heap_node< P, T > *node)
	Insert a new node `node` in the heap.
void	link (internal::fibonacci_heap_node< P, T > lhs, internal::fibonacci_heap_node< P, T > rhs)
	The node `lhs` is removed from the root list and becomes a subtree of node `rhs`.
int	remove (internal::fibonacci_heap_node< P, T > *node)
	Remove node `node` from the child list of its parent node.
void	soft_clear_ ()
	Clear the heap but do NOT delete elements.
Private Attributes
internal::fibonacci_heap_node < P, T > *	min_root
	FIXME: ugly but we need to be able to soft_clear() the heap in the copy constructor...
long	num_marked_nodes
long	num_nodes
long	num_trees

Detailed Description

template<typename P, typename T>
class mln::util::fibonacci_heap< P, T >

Fibonacci heap.

Definition at line 117 of file fibonacci_heap.hh.

Member Typedef Documentation

typedef Object<void> mln::Object< fibonacci_heap< P, T > >::category [inherited]

Definition at line 174 of file object.hh.

template<typename P, typename T>

typedef T mln::util::fibonacci_heap< P, T >::element

Definition at line 121 of file fibonacci_heap.hh.

typedef fibonacci_heap< P, T > mln::Object< fibonacci_heap< P, T > >::exact_t [inherited]

Definition at line 173 of file object.hh.

Constructor & Destructor Documentation

template<typename P , typename T >

mln::util::fibonacci_heap< P, T >::fibonacci_heap ( ) [inline]

Default constructor.

Definition at line 472 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::soft_clear_().

template<typename P , typename T >

mln::util::fibonacci_heap< P, T >::fibonacci_heap ( const fibonacci_heap< P, T > & node ) [inline]

Copy constructor Be ware that once this heap is constructed, the argument node is cleared and all its elements are part of this new heap.

Definition at line 480 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root, mln::util::fibonacci_heap< P, T >::num_marked_nodes, mln::util::fibonacci_heap< P, T >::num_nodes, and mln::util::fibonacci_heap< P, T >::num_trees.

template<typename P , typename T >

mln::util::fibonacci_heap< P, T >::~fibonacci_heap ( ) [inline]

Definition at line 499 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::clear().

Member Function Documentation

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::add_to_root_list ( internal::fibonacci_heap_node< P, T > * x ) [inline, private]

Definition at line 920 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::insert(), mln::util::internal::fibonacci_heap_node< P, T >::mark(), mln::util::fibonacci_heap< P, T >::num_marked_nodes, mln::util::fibonacci_heap< P, T >::num_nodes, and mln::util::internal::fibonacci_heap_node< P, T >::set_mark().

Referenced by mln::util::fibonacci_heap< P, T >::consolidate(), and mln::util::fibonacci_heap< P, T >::cut().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::cascading_cut ( internal::fibonacci_heap_node< P, T > * y ) [inline, private]

Cuts each node in parent list, putting successive ancestor nodes on the root list until we either arrive at the root list or until we find an ancestor that is unmarked.

When a mark is set (which only happens during a cascading cut), it means that one child subtree has been lost; if a second subtree is lost later during another cascading cut, then we move the node to the root list so that it can be re-balanced on the next consolidate.

Definition at line 954 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::cut(), mln::util::internal::fibonacci_heap_node< P, T >::mark(), mln::util::fibonacci_heap< P, T >::num_marked_nodes, and mln::util::internal::fibonacci_heap_node< P, T >::parent().

Referenced by mln::util::fibonacci_heap< P, T >::decrease_key().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::clear ( ) [inline]

Clear all elements in the heap and make the heap empty.

Definition at line 723 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root, and mln::util::fibonacci_heap< P, T >::pop_front().

Referenced by mln::util::fibonacci_heap< P, T >::~fibonacci_heap().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::consolidate ( ) [inline, private]

Internal function that reorganizes heap as part of an pop_front().

We must find new minimum in heap, which could be anywhere along the root list. The search could be O(n) since all nodes could be on the root list. So, we reorganize the tree into more of a binomial forest structure, and then find the new minimum on the consolidated O(lg n) sized root list, and in the process set each Parent pointer to 0, and count the number of resulting subtrees.

Note that after a list of n inserts, there will be n nodes on the root list, so the first pop_front() will be O(n) regardless of whether or not we consolidate. However, the consolidation causes subsequent pop_front() operations to be O(lg n). Furthermore, the extra cost of the first pop_front() is covered by the higher amortized cost of insert(), which is the real governing factor in how costly the first pop_front() will be.

Definition at line 821 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::add_to_root_list(), mln::util::internal::fibonacci_heap_node< P, T >::degree(), mln::util::fibonacci_heap< P, T >::exchange(), mln::util::fibonacci_heap< P, T >::link(), mln::util::fibonacci_heap< P, T >::min_root, mln::util::fibonacci_heap< P, T >::num_trees, and mln::util::internal::fibonacci_heap_node< P, T >::right().

Referenced by mln::util::fibonacci_heap< P, T >::pop_front().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::cut	(	internal::fibonacci_heap_node< P, T > *	lhs,
		internal::fibonacci_heap_node< P, T > *	rhs
	)			`[inline, private]`

Remove node lhs from the child list of its parent node rhs.

Definition at line 934 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::add_to_root_list(), mln::util::internal::fibonacci_heap_node< P, T >::child(), mln::util::internal::fibonacci_heap_node< P, T >::degree(), mln::util::internal::fibonacci_heap_node< P, T >::left(), mln::util::internal::fibonacci_heap_node< P, T >::right(), and mln::util::internal::fibonacci_heap_node< P, T >::set_degree().

Referenced by mln::util::fibonacci_heap< P, T >::cascading_cut(), and mln::util::fibonacci_heap< P, T >::decrease_key().

template<typename P , typename T >

int mln::util::fibonacci_heap< P, T >::decrease_key	(	internal::fibonacci_heap_node< P, T > *	node,
		internal::fibonacci_heap_node< P, T > &	key
	)			`[inline, private]`

Allow to change a node value.

FIXME: cannot use that function efficiently except by passing the node pointer. Any idea? FIXME: may be part of the public interface.

Definition at line 654 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::cascading_cut(), mln::util::fibonacci_heap< P, T >::cut(), mln::util::fibonacci_heap< P, T >::min_root, and mln::util::internal::fibonacci_heap_node< P, T >::parent().

Referenced by mln::util::fibonacci_heap< P, T >::remove().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::exchange	(	internal::fibonacci_heap_node< P, T > *&	lhs,
		internal::fibonacci_heap_node< P, T > *&	rhs
	)			`[inline, private]`

Swap the two given nodes.

Definition at line 1019 of file fibonacci_heap.hh.

Referenced by mln::util::fibonacci_heap< P, T >::consolidate().

template<typename P , typename T >

const T & mln::util::fibonacci_heap< P, T >::front ( ) const [inline]

Return the minimum value in the heap.

Definition at line 569 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root.

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::insert ( internal::fibonacci_heap_node< P, T > * node ) [inline, private]

Insert a new node node in the heap.

Definition at line 979 of file fibonacci_heap.hh.

References mln::util::internal::fibonacci_heap_node< P, T >::left(), mln::util::fibonacci_heap< P, T >::min_root, mln::util::fibonacci_heap< P, T >::num_nodes, mln::util::fibonacci_heap< P, T >::num_trees, mln::util::internal::fibonacci_heap_node< P, T >::right(), mln::util::internal::fibonacci_heap_node< P, T >::set_left(), mln::util::internal::fibonacci_heap_node< P, T >::set_parent(), and mln::util::internal::fibonacci_heap_node< P, T >::set_right().

Referenced by mln::util::fibonacci_heap< P, T >::add_to_root_list(), and mln::util::fibonacci_heap< P, T >::push().

template<typename P , typename T >

bool mln::util::fibonacci_heap< P, T >::is_empty ( ) const [inline]

Is it empty?

Definition at line 705 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root.

Referenced by mln::util::fibonacci_heap< P, T >::pop_front(), and mln::util::fibonacci_heap< P, T >::push().

template<typename P , typename T >

bool mln::util::fibonacci_heap< P, T >::is_valid ( ) const [inline]

return false if it is empty.

Definition at line 714 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root.

Referenced by mln::util::fibonacci_heap< P, T >::pop_front().

template<typename P , typename T >

void mln::util::fibonacci_heap< P, T >::link	(	internal::fibonacci_heap_node< P, T > *	lhs,
		internal::fibonacci_heap_node< P, T > *	rhs
	)			`[inline, private]`

The node lhs is removed from the root list and becomes a subtree of node rhs.

Definition at line 879 of file fibonacci_heap.hh.

Referenced by mln::util::fibonacci_heap< P, T >::consolidate().

template<typename P , typename T >

unsigned mln::util::fibonacci_heap< P, T >::nelements ( ) const [inline]

Return the number of elements.

Definition at line 745 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::num_nodes.

template<typename P , typename T >

fibonacci_heap< P, T > & mln::util::fibonacci_heap< P, T >::operator= ( fibonacci_heap< P, T > & rhs ) [inline]

Assignment operator.

Be ware that this operator do *not* copy the data from rhs to this heap. It moves all elements which means that afterwards, rhs is is cleared and all its elements are part of this new heap.

Definition at line 754 of file fibonacci_heap.hh.

References mln::util::fibonacci_heap< P, T >::min_root, mln::util::fibonacci_heap< P, T >::num_marked_nodes, mln::util::fibonacci_heap< P, T >::num_nodes, mln::util::fibonacci_heap< P, T >::num_trees, and mln::util::fibonacci_heap< P, T >::soft_clear_().

template<typename P , typename T >

T mln::util::fibonacci_heap< P, T >::pop_front ( ) [inline]

Return and remove the minimum value in the heap.

Definition at line 578 of file fibonacci_heap.hh.

References mln::util::internal::fibonacci_heap_node< P, T >::child(), mln::util::fibonacci_heap< P, T >::consolidate(), mln::util::fibonacci_heap< P, T >::is_empty(), mln::util::fibonacci_heap< P, T >::is_valid(), mln::util::internal::fibonacci_heap_node< P, T >::left(), mln::util::internal::fibonacci_heap_node< P, T >::mark(), mln::util::fibonacci_heap< P, T >::min_root, mln::util::fibonacci_heap< P, T >::num_marked_nodes, mln::util::fibonacci_heap< P, T >::num_nodes, mln::util::fibonacci_heap< P, T >::push(), mln::util::internal::fibonacci_heap_node< P, T >::right(), mln::util::internal::fibonacci_heap_node< P, T >::set_child(), mln::util::internal::fibonacci_heap_node< P, T >::set_degree(), mln::util::internal::fibonacci_heap_node< P, T >::set_left(), mln::util::internal::fibonacci_heap_node< P, T >::set_mark(), mln::util::internal::fibonacci_heap_node< P, T >::set_parent(), mln::util::internal::fibonacci_heap_node< P, T >::set_right(), and mln::util::internal::fibonacci_heap_node< P, T >::value().

Referenced by mln::util::fibonacci_heap< P, T >::clear(), and mln::util::fibonacci_heap< P, T >::remove().

template<typename P , typename T >

std::ostream & mln::util::fibonacci_heap< P, T >::print_	(	std::ostream &	ostr,
		internal::fibonacci_heap_node< P, T > *	tree = `0`,
		internal::fibonacci_heap_node< P, T > *	parent = `0`
	)			const