Auxiliary Data Structures
[Data Structures]


Detailed Description

This group describes the data structures implemented in LEMON in order to make it easier to implement combinatorial algorithms.


Files

file  bin_heap.h
 Binary Heap implementation.
file  fib_heap.h
 Fibonacci Heap implementation.
file  linear_heap.h
 Binary Heap implementation.
file  radix_heap.h
 Radix Heap implementation.
file  radix_sort.h
 Radix sort.
file  unionfind.h
 Union-Find data structures.

Modules

 Tools to Make It Easier to Make Graph Maps
 Tools to Make It Easier to Make Graph Maps.

Classes

class  BinHeap
 A Binary Heap implementation. More...
class  FibHeap
 Fibonacci Heap. More...
class  LinearHeap
 A Linear Heap implementation. More...
class  UnionFind
 A Union-Find data structure implementation. More...
class  UnionFindEnum
 A Union-Find data structure implementation which is able to enumerate the components. More...

Functions

template<typename Iterator, typename Functor>
void lemon::radixSort (Iterator first, Iterator last, Functor functor)
 Sorts the stl compatible range into ascending order.
template<typename Iterator, typename Functor>
void lemon::counterSort (Iterator first, Iterator last, Functor functor)
 Sorts stable the stl compatible range into ascending order.


Function Documentation

void lemon::radixSort Iterator  first,
Iterator  last,
Functor  functor
 

The radixSort sorts the stl compatible range into ascending order. The radix sort algorithm can sort the items which mapped to an integer by the adaptable unary function functor and the order will be ascending by these mapped values. As function specialization there is possible to use a normal function as the functor object or if the functor is not given it will use an identity function instead.

This implemented radix sort is a special quick sort which pivot value is choosen to partite the items on the next bit. This way, let be c the maximal capacity and n the number of the items in the container, the time complexity of the algorithm O(log(c)*n) and the additional space complexity is O(log(c)).

Parameters:
first The begin of the given range.
last The end of the given range.
functor An adaptible unary function or a normal function which maps the items to any integer type which can be wheter signed or unsigned.

void lemon::counterSort Iterator  first,
Iterator  last,
Functor  functor
 

The counterSort sorts the stl compatible range into ascending order. The counter sort algorithm can sort the items which mapped to an integer by the adaptable unary function functor and the order will be ascending by these mapped values. As function specialization there is possible to use a normal function as the functor object or if the functor is not given it will use an identity function instead.

This implemented counter sort use a radix forward sort on the bytes of the integer. The algorithm can sort the items on a given byte. First time it counts how many times occurs a byte value in the container. By the occurence number it is possible to copy the container in the right order in O(n) time. The algorithm sorts the container by each bytes in forward direction which sorts the container by the whole value. This way, let be c the maximal capacity of the integer type and n the number of the items in the container, the time complexity of the algorithm O(log(c)*n) and the additional space complexity is O(n).

This sorting algorithm is stable so the order of two equal element stay in the same order.

Parameters:
first The begin of the given range.
last The end of the given range.
functor An adaptible unary function or a normal function which maps the items to any integer type which can be wheter signed or unsigned.


Generated on Fri Feb 3 18:40:00 2006 for LEMON by  doxygen 1.4.6