cartesian tree

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

data structure

Treap / Randomized cartesian tree

A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity

data structure

A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence