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).