How to find the first $k$ points of high enough level using a priority search tree?
The tree is binary and has depth $O(\log(n))$ and the properties that:


for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent.
for any node $v$, all descendants in the left subtree have x-coordinate smaller than $v$, and all descendants in the right subtree have x-coordinate larger than $v$.


This means that your solution set from which you choose $k$ elements is actually a subtree one side (in the left/right sense) of what remains when a path is deleted, and can be traversed with DFS in $(\log(n)+k)$ time.  Note that the priority search tree may require dummy points at which you root subtrees to keep the depth low.

This paper may give some clarification: http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf