# 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

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??

• What did you try first in order to mathematically prove that your approach works? – jbapple Sep 21 '19 at 2:04
• An attempt at a mathematical proof usually doesn't stop as early as yours did. It often involves making suppositions, attempting induction proofs, testing medium cases and devising lemmata. If you're not comfortable with these yet, that's OK! But the best way to learn how to analyze data structures will definitely involve understanding how to read and write proofs, so I'd suggest going back to your algorithms textbook and doing some end-of-chapter exercises. – jbapple Sep 26 '19 at 2:03
• 2. would yield satisfies by mere lucky coincidence, only - what if not? – greybeard Sep 29 '19 at 6:36
• Exercise 10.2 from Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational geometry seems to make the $O(n)$ claim quoted. – greybeard Sep 29 '19 at 11:46
• I have seen this question in that book by all means, make it a habit to properly attribute content you didn't originate. And to not change around a question while a bounty is pending, clarifications excepted. – greybeard Sep 29 '19 at 13:19

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

• And what if we start building the BST by taking the middle element as root, then the middle of the left half as the root of the left subtree and the middle element of the right half as the root of the right subtree. Shouldn't the BST constructed in this way be balanced and take O(n) time? – Siladittya Sep 20 '19 at 8:34
• No you are getting it wrong. Think of it as inserting $N$ elements where insertion of each element takes $O(h)$ where $h=log(N)$ if the tree is balanced. So time complexity for creating the tree is $O(NlogN)$ – tanmay_freak Sep 20 '19 at 19:27
• Have a look at this link rhyscitlema.com/algorithms/sorted-list-to-complete-bst – Siladittya Sep 27 '19 at 14:48
• You should note it says Sorted List, which you don't have. If you have points sorted before hand then you could construct the balanced BST in $O(N)$ time. But unless you have the points sorted it will take $O(NlogN)$ no matter how you construct it. – tanmay_freak Sep 28 '19 at 9:37
• I mentioned that in my question. I hope you noticed that. – Siladittya Sep 28 '19 at 9:40

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.