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