finding an algorithm for creating a priority search tree in linear time with presorting

Question

A priority search tree is a binary tree satisfying the following:

• every node $u$ stores a point $p_u = (x_u,y_u)$
• every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate.
• If $v$ is a descendant of $u, y_v\leq y_u$.
• If $v$ is in the left subtree of $u$, then $x_v < x_u$ and if $v$ is in the right subtree of $u$, then $x_v \ge x_u$.

Source: the above definition is a variant of the one used in this question: Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

I was wondering how, if given a set of $n$ points in general position sorted by $x$-coordinate, one could construct a priority search tree in worst case linear time?

I know how to create a priority search tree in $O(n\log n)$ worst case time. I thought of creating a BST of x-coordinates and then doing an in-place fix with rotations to ensure the heap property is maintained. For each node $u,$ we can then let $x_u'=x_u$, the x-coordinate of the point it stores. However, this algorithm doesn't seem to run in linear time (since while doing the in-place fix the number of rotations could be close to linear for many points).

Answer 1

What you are looking for is essentially a Cartesian tree:

The Cartesian tree for a sequence of distinct numbers can be uniquely defined by the following properties:

1. The Cartesian tree for a sequence has one node for each number in the sequence. Each node is associated with a single sequence value.
2. A symmetric (in-order) traversal of the tree results in the original sequence. That is, the left subtree consists of the values earlier than the root in the sequence order, while the right subtree consists of the values later than the root, and a similar ordering constraint holds at each lower node of the tree.
3. The tree has the heap property: the parent of any non-root node has a smaller value than the node itself.

Just transform the $n$ points $p_0,p_1,\ldots,p_n$ where $x_0\le x_1\le \cdots \le x_n$ into an array $A$ where $A[i]=-y_i$, and construct the Cartesian tree for this array. The Cartesian tree meets all your requirements.

There are several methods to construct a Cartesian tree in linear time. I quote a simple one from Wikipedia here:

One method is to simply process the sequence values in left-to-right order, maintaining the Cartesian tree of the nodes processed so far, in a structure that allows both upwards and downwards traversal of the tree. To process each new value x, start at the node representing the value prior to x in the sequence and follow the path from this node to the root of the tree until finding a value y smaller than x. The node x becomes the right child of y, and the previous right child of y becomes the new left child of x. The total time for this procedure is linear, because the time spent searching for the parent y of each new node x can be charged against the number of nodes that are removed from the rightmost path in the tree.