Loading...
Searching...
No Matches
HeapUnionFind< V, IM, Comp > Class Template Reference
Data Structures » Auxiliary Data Structures

## Detailed Description

template<typename V, typename IM, typename Comp = std::less<V>>
class lemon::HeapUnionFind< V, IM, Comp >

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.

Precondition
  You need to add all the elements by the insert() method.

`#include <lemon/unionfind.h>`

## Classes

class | ItemIt
| LEMON style iterator for the items of a class. More...
class | ClassIt
| Class iterator. More...

## Public Types

typedef V | Value
typedef IM::Key | Item
typedef IM | ItemIntMap
typedef Comp | Compare

## Public Member Functions

bool | alive (int cls) const
| Returns true when the given class is alive.
bool | trivial (int cls) const
| Returns true when the given class is trivial.
| HeapUnionFind (ItemIntMap &_index)
| Constructs the union-find.
void | clear ()
| Clears the union-find data structure.
int | insert (const Item &item, const Value &prio)
| Insert a new node into a new component.
int | find (const Item &item) const
| The class of the item.
template<typename Iterator>
int | join (Iterator begin, Iterator end)
| Joins the classes.
template<typename Iterator>
void | split (int cls, Iterator out)
| Split the class to subclasses.
const Value & | operator[] (const Item &item) const
| Gives back the priority of the current item.
void | set (const Item &item, const Value &prio)
| Sets the priority of the current item.
void | increase (const Item &item, const Value &prio)
| Increase the priority of the current item.
void | decrease (const Item &item, const Value &prio)
| Increase the priority of the current item.
const Value & | classPrio (int cls) const
| Gives back the minimum priority of the class.
const Item & | classTop (int cls) const
| Gives back the minimum priority item of the class.
const Item & | classRep (int id) const
| Gives back a representant item of the class.

## Constructor & Destructor Documentation

## HeapUnionFind()

template<typename V, typename IM, typename Comp = std::less<V>>

HeapUnionFind | ( | ItemIntMap & | _index | ) |

inline

Constructs the union-find.

_index The index map of the union-find. The data structure uses internally for store references.

## Member Function Documentation

## alive()

template<typename V, typename IM, typename Comp = std::less<V>>

bool alive | ( | int | cls | ) | const

inline

Returns true when the given class is alive, ie. the class is not nested into other class.

## trivial()

template<typename V, typename IM, typename Comp = std::less<V>>

bool trivial | ( | int | cls | ) | const

inline

Returns true when the given class is trivial, ie. the class contains just one item directly.

## clear()

template<typename V, typename IM, typename Comp = std::less<V>>

void clear | ( |  | ) |

inline

Erase each item from the data structure.

## insert()

template<typename V, typename IM, typename Comp = std::less<V>>

int insert | ( | const Item & | item,
|  | const Value & | prio )

inline

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.

## find()

template<typename V, typename IM, typename Comp = std::less<V>>

int find | ( | const Item & | item | ) | const

inline

Returns
  The alive class id of the item, which is not nested into other classes.

The time complexity is O(log(n)).

## join()

template<typename V, typename IM, typename Comp = std::less<V>>
template<typename Iterator>

int join | ( | Iterator | begin,
|  | Iterator | end )

inline

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.

Precondition
  The range should contain at least two class ids.

## split()

template<typename V, typename IM, typename Comp = std::less<V>>
template<typename Iterator>

void split | ( | int | cls,
|  | Iterator | out )

inline

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.

## operator[]()

template<typename V, typename IM, typename Comp = std::less<V>>

const Value & operator[] | ( | const Item & | item | ) | const

inline

Gives back the priority of the current item.

## set()

template<typename V, typename IM, typename Comp = std::less<V>>

void set | ( | const Item & | item,
|  | const Value & | prio )

inline

Sets the priority of the current item.

## increase()

template<typename V, typename IM, typename Comp = std::less<V>>

void increase | ( | const Item & | item,
|  | const Value & | prio )

inline

Increase the priority of the current item.

## decrease()

template<typename V, typename IM, typename Comp = std::less<V>>

void decrease | ( | const Item & | item,
|  | const Value & | prio )

inline

Increase the priority of the current item.

## classPrio()

template<typename V, typename IM, typename Comp = std::less<V>>

const Value & classPrio | ( | int | cls | ) | const

inline

Gives back the minimum priority of the class.

## classTop()

template<typename V, typename IM, typename Comp = std::less<V>>

const Item & classTop | ( | int | cls | ) | const

inline

Returns
  Gives back the minimum priority item of the class.

## classRep()

template<typename V, typename IM, typename Comp = std::less<V>>

const Item & classRep | ( | int | id | ) | const

inline

Gives back a representant item of the class. The representant is indpendent from the priorities of the items.