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 &cout, 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.

Member Typedef Documentation

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

template<typename P, typename T>

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

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

Constructor & Destructor Documentation

template<typename P , typename T >

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

Default constructor.

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.

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]

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]

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.

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.

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.

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.

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.

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.

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.

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.

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?

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.

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.

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.

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.

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.

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 &	cout,
		internal::fibonacci_heap_node< P, T > *	tree = `0`,
		internal::fibonacci_heap_node< P, T > *	parent = `0`
	)			const