Priority Search Trees
Edward M. McCreight · SIAM Journal on Computing · 1985
Let D be a dynamic set of ordered pairs $[ x,y ]$ over the set $0,1, \cdots ,k - 1$ of integers. Consider the following operations applied to D: (1) Insert (delete) a pair $[ x,y ]$ into (from) D. (2) Given test integers $x0,x1$, and $y1$, among all pairs $[ x,y ]$ in D such that $x0 \leqq x \leqq x1$ and $y \leqq y1$, find a pair whose x is minimal (or maximal). (3) Given test integers $x0$ and $x1$, among all pairs $[ x,y ]$ in D such that $x0 \leqq x \leqq x1$, find a pair whose y is minimal. (4) Given test integers $x0$, $x1$, and $y1$, enumerate those pairs $[x,y ]$ in D such that $x0 \leqq x \leqq x1$ and $y \leqq y1$. Using a new data structure that we call a priority search tree, of which two variants are introduced, operations (1), (2), and (3) can be implemented in $O(\log n)$ time, where n is the cardinality of D. Operation (4) is performed in at most $O(\log n + s)$ time, where s is the number of pairs enumerated. The priority search tree occupies $O(n)$ space. Priority seach tree algorithms can be used effectively as subroutines in diverse applications. With them one can answer questions of intersection or containment in a dynamic set of linear intervals. They can be used in combination with a well-known plane-sweep technique, to implement off-line algorithms for enumerating all intersecting pairs of rectangles. Priority search trees can also be used to implement best-/first-fit storage allocation.