tag

#cartesian-tree

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Cartesian Tree Adaptive Sort

Cartesian Tree Adaptive Sort Cartesian tree adaptive sort builds a Cartesian tree from the input sequence and uses its structure to produce sorted output. The tree encodes both the order of elements and their relative values. You use it when input has structure that can be exploited through tree shape. Problem Given an array ( A ), sort it by: constructing a Cartesian tree extracting elements in sorted order A...

Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Cartesian Tree Sort

Cartesian Tree Sort Cartesian tree sort builds a Cartesian tree from the input array, then uses traversal to produce a sorted sequence. A Cartesian tree is a binary tree that satisfies both: heap property on values inorder traversal reproduces the original sequence For sorting, the tree is typically built as a min-heap, so the root holds the smallest element. Problem Given a sequence $A$ of length $n$, reorder it such...