Template Function ADS::cartesianTree

• Defined in File RangeMinimum.h

Function Documentation

template<class T, class Compare = std::less<T>>
std::vector<std::size_t> ADS::cartesianTree(const std::vector<T> &A, Compare less = {})

the parent of each item of A in its Cartesian tree, the root (the leftmost minimum) having A.size(); equal items go to the right

Post:

a heap: no item is smaller than its parent (an audit)