Cartesian trees: preserve sequence order under a heap minimum

Last updated: 4 Oct 20269 min read

tutorial

A min Cartesian tree has two simultaneous invariants: its in-order traversal follows the original sequence positions, and each parent is no greater than its children. This implementation uses the pair (reading, position) to break equal-value ties toward the earlier position. A monotone stack builds parent, left, and right arrays in one scan. The range minimum between two positions is the value at their lowest common ancestor. This version finds that ancestor by walking parent chains directly; it does not precompute a constant-time LCA table. The input is a static sequence, not a set of distinct keys, so comparing by reading alone would leave duplicate ownership ambiguous.

Operational case

Daily inspection readings are 47, 19, 19, 61, 29, and 83. The first 19 becomes the root because the equal 19 at the next position loses the tie. The minimum from positions one through four is 19 at position one; the minimum from positions three through five is 29 at position four. A caller may ask a range whose endpoints are equal, which returns that reading. Empty or reversed intervals fail instead of producing an accidental Python slice result. Inserting another reading between days changes sequence positions and invalidates the tree, so a new static build is required.

Working Python program

class CartesianReadingIndex:
    def __init__(self, readings):
        self.readings = list(readings)
        count = len(readings)
        self.parent = [None] * count
        self.left = [None] * count
        self.right = [None] * count
        stack = []
        for index, value in enumerate(readings):
            displaced = None
            while stack and (value, index) < (readings[stack[-1]], stack[-1]):
                displaced = stack.pop()
            if stack:
                self.right[stack[-1]] = index
                self.parent[index] = stack[-1]
            if displaced is not None:
                self.left[index] = displaced
                self.parent[displaced] = index
            stack.append(index)
        self.root = stack[0] if stack else None

    def minimum(self, first, last):
        if not 0 <= first <= last < len(self.readings):
            raise IndexError("invalid inclusive reading range")
        ancestors = set()
        cursor = first
        while cursor is not None:
            ancestors.add(cursor)
            cursor = self.parent[cursor]
        cursor = last
        while cursor not in ancestors:
            cursor = self.parent[cursor]
        return self.readings[cursor], cursor


index = CartesianReadingIndex([47, 19, 19, 61, 29, 83])
print(index.root, index.minimum(1, 4), index.minimum(3, 5))

Output

1 (19, 1) (29, 4)

Time, space, and tradeoff

The monotone stack pushes and pops each of N indices at most once, giving O(N) construction time and O(N) arrays and stack space. A direct ancestor query takes O(H) time and O(H) temporary set space for tree height H; H can be N on monotone input. That limitation is deliberate. Binary lifting would add O(N log N) preprocessing and memory for O(log N) LCA queries; a more specialized static RMQ representation can do better still. This page separates the tree invariant from a particular LCA accelerator. It is useful for understanding why a range minimum can be reduced to ancestry, not as the fastest ready-made range-query engine.

Common Mistakes

Do not sort the readings before building the tree; position order is part of the invariant.
Do not treat equal values as an unspecified tie.
Do not call this direct-ancestor query constant time.
Do not mutate the sequence without rebuilding its parent links.

Connected lessons

Compare its update and query contract with Eytzinger arrays: store a search tree in breadth-first order, Leftist heaps: keep the right spine short for meld, Potential disjoint sets: preserve numeric differences across merges, then complete the structure audit and decision quiz.

data structures

trees-and-heaps