Fibonacci heap. More...
#include <fibonacci_heap.hh>
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 |
Fibonacci heap.
Definition at line 117 of file fibonacci_heap.hh.
typedef Object<void> mln::Object< fibonacci_heap< P, T > >::category [inherited] |
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] |
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_().
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.
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().
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().
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().
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().
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().
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().
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().
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().
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.
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().
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().
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().
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.
References 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 >::mark(), mln::util::fibonacci_heap< P, T >::num_marked_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_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(), and mln::util::internal::fibonacci_heap_node< P, T >::set_right().
Referenced by mln::util::fibonacci_heap< P, T >::consolidate().
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.
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_().
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().
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 |
Definition at line 770 of file fibonacci_heap.hh.
References mln::util::internal::fibonacci_heap_node< P, T >::child(), mln::util::internal::fibonacci_heap_node< P, T >::left(), mln::util::fibonacci_heap< P, T >::min_root, mln::util::internal::fibonacci_heap_node< P, T >::parent(), mln::util::internal::fibonacci_heap_node< P, T >::print_(), mln::util::internal::fibonacci_heap_node< P, T >::right(), and mln::util::internal::fibonacci_heap_node< P, T >::value().
void mln::util::fibonacci_heap< P, T >::push | ( | fibonacci_heap< P, T > & | other_heap | ) | [inline] |
Take other_heap's
elements and insert them in this heap.
After this call other_heap
is cleared.
Definition at line 520 of file fibonacci_heap.hh.
References mln::util::fibonacci_heap< P, T >::is_empty(), 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, 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_right(), and mln::util::fibonacci_heap< P, T >::soft_clear_().
void mln::util::fibonacci_heap< P, T >::push | ( | const P & | priority, | |
const T & | value | |||
) | [inline] |
Push a new element in the heap.
Definition at line 508 of file fibonacci_heap.hh.
References mln::util::fibonacci_heap< P, T >::insert().
Referenced by mln::util::fibonacci_heap< P, T >::pop_front().
int mln::util::fibonacci_heap< P, T >::remove | ( | internal::fibonacci_heap_node< P, T > * | node | ) | [inline, private] |
Remove node node
from the child list of its parent node.
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 681 of file fibonacci_heap.hh.
References mln::util::fibonacci_heap< P, T >::decrease_key(), and mln::util::fibonacci_heap< P, T >::pop_front().
void mln::util::fibonacci_heap< P, T >::soft_clear_ | ( | ) | [inline, private] |
Clear the heap but do *NOT* delete elements.
Definition at line 733 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.
Referenced by mln::util::fibonacci_heap< P, T >::fibonacci_heap(), mln::util::fibonacci_heap< P, T >::operator=(), and mln::util::fibonacci_heap< P, T >::push().
internal::fibonacci_heap_node<P,T>* mln::util::fibonacci_heap< P, T >::min_root [mutable, private] |
FIXME: ugly but we need to be able to soft_clear() the heap in the copy constructor...
Any idea how to do without that?
Definition at line 238 of file fibonacci_heap.hh.
Referenced by mln::util::fibonacci_heap< P, T >::clear(), mln::util::fibonacci_heap< P, T >::consolidate(), mln::util::fibonacci_heap< P, T >::decrease_key(), mln::util::fibonacci_heap< P, T >::fibonacci_heap(), mln::util::fibonacci_heap< P, T >::front(), mln::util::fibonacci_heap< P, T >::insert(), mln::util::fibonacci_heap< P, T >::is_empty(), mln::util::fibonacci_heap< P, T >::is_valid(), mln::util::fibonacci_heap< P, T >::operator=(), mln::util::fibonacci_heap< P, T >::pop_front(), mln::util::fibonacci_heap< P, T >::print_(), mln::util::fibonacci_heap< P, T >::push(), and mln::util::fibonacci_heap< P, T >::soft_clear_().
long mln::util::fibonacci_heap< P, T >::num_marked_nodes [mutable, private] |
Definition at line 241 of file fibonacci_heap.hh.
Referenced by mln::util::fibonacci_heap< P, T >::add_to_root_list(), mln::util::fibonacci_heap< P, T >::cascading_cut(), mln::util::fibonacci_heap< P, T >::fibonacci_heap(), mln::util::fibonacci_heap< P, T >::link(), mln::util::fibonacci_heap< P, T >::operator=(), mln::util::fibonacci_heap< P, T >::pop_front(), mln::util::fibonacci_heap< P, T >::push(), and mln::util::fibonacci_heap< P, T >::soft_clear_().
long mln::util::fibonacci_heap< P, T >::num_nodes [mutable, private] |
Definition at line 239 of file fibonacci_heap.hh.
Referenced by mln::util::fibonacci_heap< P, T >::add_to_root_list(), mln::util::fibonacci_heap< P, T >::fibonacci_heap(), mln::util::fibonacci_heap< P, T >::insert(), mln::util::fibonacci_heap< P, T >::nelements(), mln::util::fibonacci_heap< P, T >::operator=(), mln::util::fibonacci_heap< P, T >::pop_front(), mln::util::fibonacci_heap< P, T >::push(), and mln::util::fibonacci_heap< P, T >::soft_clear_().
long mln::util::fibonacci_heap< P, T >::num_trees [mutable, private] |
Definition at line 240 of file fibonacci_heap.hh.
Referenced by mln::util::fibonacci_heap< P, T >::consolidate(), mln::util::fibonacci_heap< P, T >::fibonacci_heap(), mln::util::fibonacci_heap< P, T >::insert(), mln::util::fibonacci_heap< P, T >::link(), mln::util::fibonacci_heap< P, T >::operator=(), mln::util::fibonacci_heap< P, T >::push(), and mln::util::fibonacci_heap< P, T >::soft_clear_().