Aleph::Max_Cartesian_Tree< T > Struct Template Reference

Cartesian Tree for max-heap (range maximum). More...

#include <tpl_cartesian_tree.H>

Inheritance diagram for Aleph::Max_Cartesian_Tree< T >:

Collaboration diagram for Aleph::Max_Cartesian_Tree< T >:

Public Types
using	Base = Gen_Cartesian_Tree< T, Aleph::greater< T > >
Public Types inherited from Aleph::Gen_Cartesian_Tree< T, Aleph::greater< T > >
using	Item_Type = T
	The type of the element stored in the tree.

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Cartesian_Tree< T, Aleph::greater< T > >
	Gen_Cartesian_Tree (const Array< T > &values, Aleph::greater< T > c=Aleph::greater< T >())
	Construct from an Array<T>.
	Gen_Cartesian_Tree (const std::vector< T > &values, Aleph::greater< T > c=Aleph::greater< T >())
	Construct from a std::vector<T>.
	Gen_Cartesian_Tree (std::initializer_list< T > il, Aleph::greater< T > c=Aleph::greater< T >())
	Construct from an initializer_list<T>.
	Gen_Cartesian_Tree (const DynList< T > &values, Aleph::greater< T > c=Aleph::greater< T >())
	Construct from a DynList<T>.
	Gen_Cartesian_Tree (const size_t num, const T &init, Aleph::greater< T > c=Aleph::greater< T >())
	Construct with num elements all equal to init.
	Gen_Cartesian_Tree (const Gen_Cartesian_Tree &)=default
	Copy constructor.
	Gen_Cartesian_Tree (Gen_Cartesian_Tree &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > and std::is_nothrow_move_constructible_v< Aleph::greater< T > >)=default
Gen_Cartesian_Tree &	operator= (const Gen_Cartesian_Tree &)=default
	Copy assignment operator.
Gen_Cartesian_Tree &	operator= (Gen_Cartesian_Tree &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > and std::is_nothrow_move_assignable_v< Aleph::greater< T > >)=default
constexpr size_t	root () const noexcept
	Index of the root node.
size_t	left_child (const size_t i) const
	Left child of node i.
size_t	right_child (const size_t i) const
	Right child of node i.
size_t	parent_of (const size_t i) const
	Parent of node i.
const T &	data_at (const size_t i) const
	Value at node i.
constexpr size_t	size () const noexcept
	Number of nodes.
constexpr bool	is_empty () const noexcept
	True if the tree is empty.
bool	is_leaf (const size_t i) const
	True if node i is a leaf (no children).
bool	is_root (const size_t i) const
	True if node i is the root.
size_t	height () const
	Height of the tree (longest root-to-leaf path).
Array< size_t >	inorder () const
	Inorder traversal of the tree.
Array< T >	values () const
	Copy of the original data array.
void	swap (Gen_Cartesian_Tree &other) noexcept(noexcept(data_.swap(other.data_)) &&noexcept(parent_.swap(other.parent_)) &&noexcept(left_.swap(other.left_)) &&noexcept(right_.swap(other.right_)) &&noexcept(std::swap(root_, other.root_)) &&noexcept(std::swap(n_, other.n_)) &&std::is_nothrow_swappable_v< Aleph::greater< T > >)
	Swap with other in O(1).
Static Public Attributes inherited from Aleph::Gen_Cartesian_Tree< T, Aleph::greater< T > >
static constexpr size_t	NONE
	Sentinel value for absent parent/child links.

Detailed Description

template<std::totally_ordered T>
struct Aleph::Max_Cartesian_Tree< T >

Cartesian Tree for max-heap (range maximum).

Template Parameters

T	a totally ordered type.

Definition at line 484 of file tpl_cartesian_tree.H.

Member Typedef Documentation

Base

template<std::totally_ordered T>

using Aleph::Max_Cartesian_Tree< T >::Base = Gen_Cartesian_Tree<T, Aleph::greater<T> >

Definition at line 487 of file tpl_cartesian_tree.H.

---

The documentation for this struct was generated from the following file:

• tpl_cartesian_tree.H