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

Question

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the tree when the points are not sorted.

I am thinking of a way to do this, which is as follows:

1. Construct a BST on the points. Since the points are sorted then it will take O(n) time.

   I followed the approach given in this link for this step.

2. Check if all the nodes satisfy the min-heap property based on the x-coordinates

   This will take O(n) time.

So total time complexity will be O(n)

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates??

Answer 1

Is there a way to make PST in O(N)

The simple is answer is No. It will take a minimum $O(NlogN)$ time to construct the tree.

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates.

No, the algorithm you mentioned will fail when you try to maintain the min-heap property based on $x-coordinates$.When you perform the min-heapify operation, the $y-coordinates$ will move from original position and the property of BST (based on $y-coordinates$) will fail. You can't maintain BST property for $y-coordinates$ anymore. So the tree will just reduce to min-heap based on $x-coordinates$.

Here's a thought to construct priority search tree sorted on $Y$-coordinates:

For a given set of points $S$(sorted on $X$-coordinates), create a priority search tree as follows:

1. If $S$ is empty, return a NULL pointer and stop.

2. The point $P$ in $S$ with the greatest $Y$-coordinate becomes the root $R$.

3. If $S-P$ is an empty set , then $R$ is a leaf so we return it and stop.

4. Let $X(P)$ be a value such that half of points in $S-P$ have $X$-coordinate lower than $X(P)$, and half having higher value. Basically $X(P)$ is median(based on $X$) of your $S-P$

5. Recursively create a priority search tree on the lower half of $S-P$, let its root be the left child of $R$.

6. Recursively create a priority search tree on the upper half of $S-P$, let its root be the right child of $R$.

Total time complexity will be $O(nlogn)$ as the tree will be height balanced.

Notes:

1. Since you have sorted points based on $X$coordinates finding median will take $O(1)$.

2. To find the maximum $Y$, for simplification you could also maintain a max-heap based on $Y$. Finding maximum $Y$ from it and subsequently removing from it during creation of priority search tree will take $O(logn)$.

Answer 2

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates?

No.
In revision 8, it constructs a valid search tree on $y$.
The check in step 2 will almost always yield not satisfied.

The best I thought up, ignoring non-unique priority values:

Proceed the complete binary search tree construction as usual, annotating each node with a priority value that allows to bound searches in the sub-tree it roots.
Inserting node $k$, the path to/from the root will have a length equal the the depth of $k$, and for "the priority side of a PST under construction", its value would have to be annotated to an unknown number of nodes, worst case: to every one on this path for a total of $O(n \log n)$ construction time.
If instead of annotating this "winner", D.E. Knuth presents annotating the loser in TAoCP 5.4.1:
this is the top priority in this sub-tree without the values on the path from the root.
Here, only one node needs to be annotated, it is on the path between the node inserted in the previous step and the root, with priority increasing in this direction: one can find it in $O(\log \log n)$ steps for a total of $O(n \log \log n)$ construction time.

This does not yield a PST.
It should yield a search tree supporting $[-inf, qx] \times [qy, qy']$ queries no worse than a PST does.