Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann    

beap.hpp File Reference

Detailed Description

Several functions are provided for creation and manipulation of an interesting data structure called bi-parental heap, or beap. In short, in this data structure inner elements have two parents that are both larger than the element.

Internally, the nodes are organized by levels, starting with node 0 at level 0. Level k has k+1 nodes, numbered consecutively. Therefore, the first node on the kth level is numbered $ k*(k+1)/2 $ . The left parent of the ith node on level k is numbered $ i-k-1 $ and the right is $ i-k $ . A node at level k does not have a left parent if it is equal to $ k(k+1)/2 $ . A node at level k does not have a right parent if it is equal to $ (k+1)(k+2)/2-1 $ . The level k of a node i can be computed by solving $ k(k+1)/2=i $ , or $ k = \lfloor (\sqrt{8*i+1}-1)/2 \rfloor$ , but it is much faster to be computed by binary search.

The following collection of functions provides a space efficient implementation of the beap.

Definition in file beap.hpp.

Go to the source code of this file.

Namespaces

namespace  beap_detail

Functions

unsigned short beap_detail::my_sqrt (unsigned long a)
template<class Distance>
int beap_detail::level (Distance p)
template<class RandomAccessIterator>
bool is_beap (RandomAccessIterator first, RandomAccessIterator last)
 Returns true if [first, last) is a valid beap data structure.
template<class RandomAccessIterator, class StrictWeakOrdering>
bool is_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 Returns true if [first, last) is a valid beap data structure.
template<class RandomAccessIterator>
void make_beap (RandomAccessIterator first, RandomAccessIterator last)
 make_beap turns [first, last) into a beap. This algorithm is provided for completeness, although std::sort(first,last) achieves the same effect and has a better complexity.
template<class RandomAccessIterator, class StrictWeakOrdering>
void make_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 make_beap turns [first, last) into a beap. This algorithm is provided for completeness, although std::sort(first,last) achieves the same effect and has a better complexity.
template<class RandomAccessIterator>
RandomAccessIterator min_beap (RandomAccessIterator first, RandomAccessIterator last)
 Returns the iterator to the smallest element in the beap.
template<class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator min_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 Returns the iterator to the smallest element in the beap.
template<class RandomAccessIterator>
RandomAccessIterator max_beap (RandomAccessIterator first, RandomAccessIterator last)
 Returns the iterator to the largest element in the beap.
template<class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator max_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 Returns the iterator to the largest element in the beap.
template<class RandomAccessIterator>
void insert_beap (RandomAccessIterator first, RandomAccessIterator last)
 Adds an element to the beap and preserves beap's property. The element to be added to the beap is at iterator (last-1) .
template<class RandomAccessIterator, class StrictWeakOrdering>
void insert_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 Adds an element to the beap and preserves beap's property. The element to be added to the beap is at iterator (last-1) .
template<class T, class RandomAccessIterator>
RandomAccessIterator find_beap (RandomAccessIterator first, RandomAccessIterator last, T x)
 Returns iterator to the location of the desired element. If there is more than one appearance of the element in the beap, the returned location is not necessarily the first location in the corresponding array.
template<class T, class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator find_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp, T x)
 Returns iterator to the location of the desired element. If there is more than one appearance of the element in the beap, the returned location is not necessarily the first location in the corresponding array.
template<class RandomAccessIterator>
void sort_beap (RandomAccessIterator first, RandomAccessIterator last)
 Turns a beap [first, last) into a sorted range.
template<class RandomAccessIterator, class StrictWeakOrdering>
void sort_beap (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
 Turns a beap [first, last) into a sorted range.
template<class RandomAccessIterator>
void remove_beap (RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last)
 Removes element at position pos from the beap and adjusts the beap.
template<class RandomAccessIterator, class StrictWeakOrdering>
void remove_beap (RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last, StrictWeakOrdering comp)
 Removes element at position pos from the beap and adjusts the beap.

Function Documentation

template<class T, class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator find_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp,
T  x
) 
 

Returns iterator to the location of the desired element. If there is more than one appearance of the element in the beap, the returned location is not necessarily the first location in the corresponding array.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Postcondition:
Returns iterator to element in the beap. If element is not in the beap, last is returned
Complexity:
$ O(\sqrt{n}) $

Definition at line 440 of file beap.hpp.

template<class T, class RandomAccessIterator>
RandomAccessIterator find_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
T  x
) 
 

Returns iterator to the location of the desired element. If there is more than one appearance of the element in the beap, the returned location is not necessarily the first location in the corresponding array.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Postcondition:
Returns iterator to element in the beap. If element is not in the beap, last is returned
Complexity:
$ O(\sqrt{n}) $

Definition at line 409 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
void insert_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Adds an element to the beap and preserves beap's property. The element to be added to the beap is at iterator (last-1) .

Precondition:
  • Range [first, last-1) must be a valid beap.
Postcondition:
  • Range [first, last) is a valid beap.
Requirements on types:
Complexity:
$ O(\sqrt{n}) $

Definition at line 379 of file beap.hpp.

template<class RandomAccessIterator>
void insert_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

Adds an element to the beap and preserves beap's property. The element to be added to the beap is at iterator (last-1) .

Precondition:
  • Range [first, last-1) must be a valid beap.
Postcondition:
  • Range [first, last) is a valid beap.
Requirements on types:
Complexity:
$ O(\sqrt{n}) $

Definition at line 352 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
bool is_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Returns true if [first, last) is a valid beap data structure.

Requirements on types:
Complexity:
$ O(n) $ if n is the number of elements of [first, last)

Definition at line 136 of file beap.hpp.

template<class RandomAccessIterator>
bool is_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

Returns true if [first, last) is a valid beap data structure.

Requirements on types:
Complexity:
$ O(n) $ if n is the number of elements of [first, last)

Definition at line 119 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
void make_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

make_beap turns [first, last) into a beap. This algorithm is provided for completeness, although std::sort(first,last) achieves the same effect and has a better complexity.

Requirements on types:
Complexity:
$ O(n\sqrt{n}) $

Definition at line 172 of file beap.hpp.

template<class RandomAccessIterator>
void make_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

make_beap turns [first, last) into a beap. This algorithm is provided for completeness, although std::sort(first,last) achieves the same effect and has a better complexity.

Requirements on types:
Complexity:
$ O(n\sqrt{n}) $

Definition at line 153 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator max_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Returns the iterator to the largest element in the beap.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Complexity:
$ O(\sqrt{n}) $

Definition at line 255 of file beap.hpp.

template<class RandomAccessIterator>
RandomAccessIterator max_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

Returns the iterator to the largest element in the beap.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Complexity:
$ O(\sqrt{n}) $

Definition at line 234 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator min_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Returns the iterator to the smallest element in the beap.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Complexity:
Constant time

Definition at line 215 of file beap.hpp.

template<class RandomAccessIterator>
RandomAccessIterator min_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

Returns the iterator to the smallest element in the beap.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
Complexity:
Constant time

Definition at line 197 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
void remove_beap (  RandomAccessIterator  first,
RandomAccessIterator  pos,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Removes element at position pos from the beap and adjusts the beap.

Precondition:
Range [first, last) must be a valid beap.
Requirements on types:
Postcondition:
Range [first , last-1) is a valid beap without the element originally pointed to by pos, and *(last-1) contains that element.
Complexity:
$ O(\sqrt{n}) $

Definition at line 616 of file beap.hpp.

template<class RandomAccessIterator>
void remove_beap (  RandomAccessIterator  first,
RandomAccessIterator  pos,
RandomAccessIterator  last
) 
 

Removes element at position pos from the beap and adjusts the beap.

Precondition:
Range [first, last) must be a valid beap.
Requirements on types:
Postcondition:
Range [first, last-1) is a valid beap without the element originally pointed to by pos.
Complexity:
$ O(\sqrt{n}) $

Definition at line 591 of file beap.hpp.

template<class RandomAccessIterator, class StrictWeakOrdering>
void sort_beap (  RandomAccessIterator  first,
RandomAccessIterator  last,
StrictWeakOrdering  comp
) 
 

Turns a beap [first, last) into a sorted range.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
See also:
make_beap
Complexity:
$ O(n\sqrt{n}) $

Definition at line 562 of file beap.hpp.

template<class RandomAccessIterator>
void sort_beap (  RandomAccessIterator  first,
RandomAccessIterator  last
) 
 

Turns a beap [first, last) into a sorted range.

Precondition:
  • Range [first, last) must be a valid beap.
Requirements on types:
See also:
make_beap
Complexity:
$ O(n\sqrt{n}) $

Definition at line 540 of file beap.hpp.

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Herve Bronnimann, 2005.