HeapUnionFind
Declared in lemon/unionfind.h, in the group Auxiliary Data Structures; the same class on the Doxygen site.
-
template< typename V , typename IM , typename Comp = std::less< V > >
class HeapUnionFind A Union-Find data structure implementation which is able to store a priority for each item and retrieve the minimum of each class. In addition, it supports the joining and splitting the components. If you don’t need this feature then you makes better to use the UnionFind class which is more efficient.
The union-find data strcuture based on a (2, 16)-tree with a tournament minimum selection on the internal nodes. The insert operation takes O(1), the find, set, decrease and increase takes O(log(n)), where n is the number of nodes in the current component. The complexity of join and split is O( log(n) * k ), where n is the sum of the number of the nodes and k is the number of joined components or the number of the components after the split.
- Pre:
You need to add all the elements by the insert() method.
Public Functions
-
inline bool alive( int cls ) const
Returns true when the given class is alive.
Returns true when the given class is alive, ie. the class is not nested into other class.
-
inline bool trivial( int cls ) const
Returns true when the given class is trivial.
Returns true when the given class is trivial, ie. the class contains just one item directly.
-
inline HeapUnionFind( ItemIntMap & _index )
Constructs the union-find.
_index The index map of the union-find. The data structure uses internally for store references.
-
inline void clear()
Clears the union-find data structure.
Erase each item from the data structure.
-
inline int insert( const Item & item , const Value & prio )
Insert a new node into a new component.
- Parameters:
item – The item of the new node.
prio – The priority of the new node.
- Returns:
The class id of the one-item-heap.
-
inline int find( const Item & item ) const
The class of the item.
The time complexity is O(log(n)).
- Returns:
The alive class id of the item, which is not nested into other classes.
-
template< typename Iterator >
inline int join( Iterator begin , Iterator end ) Joins the classes.
The current function joins the given classes. The parameter is an STL range which should be contains valid class ids. The time complexity is O( log(n) * k ) where n is the overall number of the joined nodes and k is the number of classes.
- Returns:
The class of the joined classes.
- Pre:
The range should contain at least two class ids.
-
template< typename Iterator >
inline void split( int cls , Iterator out ) Split the class to subclasses.
The current function splits the given class. The join, which made the current class, stored a reference to the subclasses. The
splitClass()member restores the classes and creates the heaps. The parameter is an STL output iterator which will be filled with the subclass ids. The time complexity is O( log(n) * k ) where n is the overall number of nodes in the splitted classes and k is the number of the classes.
-
inline const Value & operator[]( const Item & item ) const
Gives back the priority of the current item.
-
inline void increase( const Item & item , const Value & prio )
Increase the priority of the current item.
-
inline void decrease( const Item & item , const Value & prio )
Decrease the priority of the current item.
-
class ItemIt
LEMON style iterator for the items of a class.
ClassIt is a lemon style iterator for the components. It iterates on the items of a class. By example if you want to iterate on each items of each classes then you may write the next code.
for( ClassIt cit( huf ) ; cit != INVALID ; ++cit ) { std::cout << "Class: "; for( ItemIt iit( huf , cit ) ; iit != INVALID ; ++iit ) { std::cout << toString( iit ) << ' ' << std::endl; } std::cout << std::endl; }
Public Functions
-
inline ItemIt()
Default constructor
-
inline ItemIt( const HeapUnionFind & huf , int cls )
-
inline ItemIt()
-
class ClassIt
Class iterator.
The iterator stores
Public Functions
-
inline ClassIt( const HeapUnionFind & huf )
-
inline ClassIt( const HeapUnionFind & huf , int cls )
-
inline operator int() const
-
inline ClassIt( const HeapUnionFind & huf )