How to find the first $k$ points of high enough level using a priority search tree? In reading Chan's paper,
Closest Point Problems Simplified on a RAM,
the following came up as a sub-problem:

Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (ordered by $x$-coordinate) which dominate $q$.

Chan asserts that this query can be answered in $O(\log n + k)$ time using a priority search tree, but doesn't give details, and the details are not clear to me. The traditional query for a priority search tree is a 3-sided range query, but this query is different because we are given a 2-sided range (an upper-right quadrant) and a maximum number of points to report. We should report the $k$ "leftmost" points in the 2-sided range.
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