Priority Search Tree

Why Priority Search Tree Matters

In two-dimensional geometric databases, geographic information systems (GIS), and scheduling engines, a fundamental query pattern is the 3-sided range query (also called a semi-infinite orthogonal range query). Given a set of $N$ points in the 2D plane, a 3-sided query asks for all points $(x, y)$ that satisfy an $x$-interval constraint and a lower bound on $y$: $x_{min} \le x \le x_{max}$ and $y \ge y_{min}$. Standard balanced binary search trees (like AVL trees or Red-Black trees) can only index one dimension efficiently, forcing $O(N)$ linear scans when filtering the second dimension. While full 2D Range Trees solve general 4-sided range queries in $O(\log N + K)$ time, they demand $O(N \log N)$ space due to nested secondary trees.

The Priority Search Tree (PST), introduced by Edward McCreight in 1985, elegantly bridges this gap. By simultaneously maintaining a Max-Heap on $y$-coordinates and a Binary Search Tree on $x$-coordinates, a PST answers 3-sided range queries in optimal $O(\log N + K)$ time—where $K$ is the number of reported points—using

When querying spatial or temporal datasets, applications frequently need to retrieve items that fall within a two-dimensional range. For example, a GIS map application may ask for all points of interest within a horizontal map span $[x_{min}, x_{max}]$ whose elevation or distance is below a threshold $y_{max}$. In computer graphics and scheduling, retrieving active intervals or objects often reduces to a 3-sided range query: $[x_{min}, x_{max}] \times [-\infty, y_{max}]$.

Traditional 2D range trees solve 4-sided orthogonal range queries in $O(\log N + k)$ time (where $k$ is the number of reported points), but they require $O(N \log N)$ space due to secondary range structures attached to every node. K-D trees consume $O(N)$ space but degenerate to $O(\sqrt{N} + k)$ query time in two dimensions. Priority Search Trees (PSTs), introduced by Edward M. McCreight in 1985, exploit the 3-sided structure of the query region to combine a Min-Heap on $y$-coordinates with a Binary Search Tree on $x$-coordinates. This hybrid dual-invariant structure answers 3-sided range queries in optimal $O(\log N + k)$ worst-case time while using strictly $O(N)$ linear space.

Core Concepts and Terminology

A Priority Search Tree represents a finite set of 2D points $P = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\}$ where $x$-coordinates are distinct (or disambiguated by unique IDs). Each node $v$ in the tree stores a point $p(v) = (x_v, y_v)$ and a discriminator key $x_{mid}(v)$.

The structure is governed by two complementary invariants:

1. Min-Heap Property on $y$: For every non-root node $v$ with parent $u$, $y(p(u)) \le y(p(v))$. The point $p(v)$ stored at node $v$ has the minimum $y$-coordinate among all points in $v$'s subtree.
2. Binary Search Tree Property on $x$: The remaining points in $v$'s subtree (excluding $p(v)$) are partitioned into left and right subtrees by $x_{mid}(v)$. All points in the left subtree have $x \le x_{mid}(v)$, and all points in the right subtree have $x > x_{mid}(v)$.

How Priority Search Tree Works, Step by Step

A Priority Search Tree supports two major operational algorithms: Construction and 3-Sided Range Search.

1. Construction Algorithm ($O(N \log N)$)

To build a PST from a list of $2\text{D}$ points $P$:

1. Base Case: If $P$ is empty, return null.
2. Min-Y Extraction: Find the point $p^* \in P$ with the minimum $y$-coordinate.
3. Partitioning: Remove $p^*$ from $P$. If $P$ is now empty, create a leaf node storing $p^*$ with $x_{mid} = x(p^*)$.
4. Median Split: Sort the remaining points by $x$-coordinate and select the median $x$-value as $x_{mid}$.
5. Recursive Splitting: Split remaining points into $P_L = \{p \in P \mid x(p) \le x_{mid}\}$ and $P_R = \{p \in P \mid x(p) > x_{mid}\}$.
6. Node Creation: Set node.left = build(P_L) and node.right = build(P_R). Return node storing $p^*$ and $x_{mid}$.

2. 3-Sided Range Query Algorithm ($O(\log N + k)$)

Given a query range $[x_{min}, x_{max}] \times [-\infty, y_{max}]$:

1. Pruning Check: If current node is null or node.point.y > y_max, stop searching this branch (Min-Heap property guarantees no descendant can satisfy $y \le y_{max}$).
2. Point Reporting: Check if $x_{min} \le \text{node.point.x} \le x_{max}$. If true, add node.point to reported results.
3. Left Recursion: If $x_{min} \le \text{node.x\_mid}$, recursively search node.left.
4. Right Recursion: If $x_{max} > \text{node.x\_mid}$, recursively search node.right.

The decision flow for 3-sided range queries is summarized below:

flowchart TD
A[Start: query_3sided node, x_min, x_max, y_max] --> B{node == null?}
B -- Yes --> C[Return]
B -- No --> D{node.point.y > y_max?}
D -- Yes --> E[Prune Subtree & Return]
D -- No --> F{x_min <= node.point.x <= x_max?}
F -- Yes --> G[Report node.point]
F -- No --> H[Skip reporting point]
G --> I{x_min <= node.x_mid?}
H --> I
I -- Yes --> J[Recurse Left: query_3sided node.left]
I -- No --> K{x_max > node.x_mid?}
J --> K
K -- Yes --> L[Recurse Right: query_3sided node.right]
K -- No --> M[Return]
L --> M

Worked Example with a Full Trace

Consider a set of $N = 6$ points in 2D space:

$$P = \{(2, 10), (3, 1), (5, 4), (7, 2), (8, 15), (11, 6)\}$$

PST Construction Walkthrough

1. Root: Minimum $y$-point is $(3, 1)$. Remaining points sorted by $x$: $[(2,10), (5,4), (7,2), (8,15), (11,6)]$. Median $x_{mid} = 7$. * $P_L = \{(2, 10), (5, 4), (7, 2)\}$, $P_R = \{(8, 15), (11, 6)\}$.

1. Left Child: Minimum $y$-point in $P_L$ is $(7, 2)$. Remaining sorted by $x$: $[(2,10), (5,4)]$. Median $x_{mid} = 2$. * $P_{LL} = \{(2, 10)\}$, $P_{LR} = \{(5, 4)\}$.

1. Left-Left Leaf: Stored point $(2, 10)$, $x_{mid} = 2$.
2. Left-Right Leaf: Stored point $(5, 4)$, $x_{mid} = 5$.
3. Right Child: Minimum $y$-point in $P_R$ is $(11, 6)$. Remaining sorted by $x$: $[(8,15)]$. Median $x_{mid} = 8$. * $P_{RL} = \{(8, 15)\}$, $P_{RR} = \emptyset$.

1. Right-Left Leaf: Stored point $(8, 15)$, $x_{mid} = 8$.

Query Execution Trace

Query Range: $x \in [4, 10], y \le 8$ ($x_{min} = 4, x_{max} = 10, y_{max} = 8$).

Implementation in Python, C++, and Java

The complete, copy-paste-runnable code implementations below demonstrate construction and 3-sided range query on a Priority Search Tree. All three programs implement identical logic, process the exact same sample dataset, and produce identical terminal output.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"


class PSTNode:
    def __init__(self, point, x_mid, left=None, right=None):
        self.point = point
        self.x_mid = x_mid
        self.left = left
        self.right = right


def build_pst(points):
    if not points:
        return None

    # Step 1: Find point with minimum y-coordinate
    min_idx = 0
    for i in range(1, len(points)):
        if points[i].y < points[min_idx].y or (points[i].y == points[min_idx].y and points[i].x < points[min_idx].x):
            min_idx = i

    p_min = points[min_idx]
    remaining = [p for i, p in enumerate(points) if i != min_idx]

    if not remaining:
        return PSTNode(p_min, p_min.x)

    # Step 2: Sort remaining points by x to find median x_mid
    remaining.sort(key=lambda p: p.x)
    mid_idx = len(remaining) // 2
    x_mid = remaining[mid_idx].x

    left_points = remaining[\:mid_idx + 1]
    right_points = remaining[mid_idx + 1:]

    left_child = build_pst(left_points)
    right_child = build_pst(right_points)

    return PSTNode(p_min, x_mid, left_child, right_child)


def query_3sided(node, x_min, x_max, y_max, result):
    if node is None:
        return

    # Min-Heap Pruning: if minimum y in subtree > y_max, abort
    if node.point.y > y_max:
        return

    # Report point if it falls in [x_min, x_max]
    if x_min <= node.point.x <= x_max:
        result.append(node.point)

    # Recurse left if range overlaps left region
    if x_min <= node.x_mid and node.left is not None:
        query_3sided(node.left, x_min, x_max, y_max, result)

    # Recurse right if range overlaps right region
    if x_max > node.x_mid and node.right is not None:
        query_3sided(node.right, x_min, x_max, y_max, result)


if __name__ == "__main__":
    pts = [Point(2, 10), Point(3, 1), Point(5, 4), Point(7, 2), Point(8, 15), Point(11, 6)]
    root = build_pst(pts)

    print("Priority Search Tree constructed with 6 points.")
    print("Query range [x_min=4, x_max=10, y_max=8]:")

    res = []
    query_3sided(root, 4, 10, 8, res)
    res.sort(key=lambda p: (p.x, p.y))

    for p in res:
        print(f"Found point: {p}")
    print(f"Total points reported: {len(res)}")

#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
    int x, y;
};

struct PSTNode {
    Point point;
    int x_mid;
    PSTNode* left;
    PSTNode* right;

    PSTNode(Point p, int mid, PSTNode* l = nullptr, PSTNode* r = nullptr)
        : point(p), x_mid(mid), left(l), right(r) {}
};

PSTNode* buildPST(std::vector<Point> points) {
    if (points.empty()) return nullptr;

    int min_idx = 0;
    for (size_t i = 1; i < points.size(); ++i) {
        if (points[i].y < points[min_idx].y ||
           (points[i].y == points[min_idx].y && points[i].x < points[min_idx].x)) {
            min_idx = i;
        }
    }

    Point p_min = points[min_idx];
    std::vector<Point> remaining;
    for (size_t i = 0; i < points.size(); ++i) {
        if (static_cast<int>(i) != min_idx) {
            remaining.push_back(points[i]);
        }
    }

    if (remaining.empty()) {
        return new PSTNode(p_min, p_min.x);
    }

    std::sort(remaining.begin(), remaining.end(),  {
        return a.x < b.x;
    });

    size_t mid_idx = remaining.size() / 2;
    int x_mid = remaining[mid_idx].x;

    std::vector<Point> left_points(remaining.begin(), remaining.begin() + mid_idx + 1);
    std::vector<Point> right_points(remaining.begin() + mid_idx + 1, remaining.end());

    PSTNode* left_child = buildPST(left_points);
    PSTNode* right_child = buildPST(right_points);

    return new PSTNode(p_min, x_mid, left_child, right_child);
}

void query3Sided(PSTNode* node, int x_min, int x_max, int y_max, std::vector<Point>& result) {
    if (!node) return;

    if (node->point.y > y_max) return;

    if (node->point.x >= x_min && node->point.x <= x_max) {
        result.push_back(node->point);
    }

    if (x_min <= node->x_mid && node->left) {
        query3Sided(node->left, x_min, x_max, y_max, result);
    }

    if (x_max > node->x_mid && node->right) {
        query3Sided(node->right, x_min, x_max, y_max, result);
    }
}

int main() {
    std::vector<Point> pts = {{2, 10}, {3, 1}, {5, 4}, {7, 2}, {8, 15}, {11, 6}};
    PSTNode* root = buildPST(pts);

    std::cout << "Priority Search Tree constructed with 6 points.\n";
    std::cout << "Query range [x_min=4, x_max=10, y_max=8]:\n";

    std::vector<Point> res;
    query3Sided(root, 4, 10, 8, res);

    std::sort(res.begin(), res.end(),  {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    for (const auto& p : res) {
        std::cout << "Found point: (" << p.x << ", " << p.y << ")\n";
    }
    std::cout << "Total points reported: " << res.size() << "\n";

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }

    static class PSTNode {
        Point point;
        int xMid;
        PSTNode left;
        PSTNode right;

        PSTNode(Point point, int xMid, PSTNode left, PSTNode right) {
            this.point = point;
            this.xMid = xMid;
            this.left = left;
            this.right = right;
        }
    }

    static PSTNode buildPST(List<Point> points) {
        if (points.isEmpty()) return null;

        int minIdx = 0;
        for (int i = 1; i < points.size(); i++) {
            if (points.get(i).y < points.get(minIdx).y ||
               (points.get(i).y == points.get(minIdx).y && points.get(i).x < points.get(minIdx).x)) {
                minIdx = i;
            }
        }

        Point pMin = points.get(minIdx);
        List<Point> remaining = new ArrayList<>();
        for (int i = 0; i < points.size(); i++) {
            if (i != minIdx) {
                remaining.add(points.get(i));
            }
        }

        if (remaining.isEmpty()) {
            return new PSTNode(pMin, pMin.x, null, null);
        }

        remaining.sort(Comparator.comparingInt(p -> p.x));

        int midIdx = remaining.size() / 2;
        int xMid = remaining.get(midIdx).x;

        List<Point> leftPoints = new ArrayList<>(remaining.subList(0, midIdx + 1));
        List<Point> rightPoints = new ArrayList<>(remaining.subList(midIdx + 1, remaining.size()));

        PSTNode leftChild = buildPST(leftPoints);
        PSTNode rightChild = buildPST(rightPoints);

        return new PSTNode(pMin, xMid, leftChild, rightChild);
    }

    static void query3Sided(PSTNode node, int xMin, int xMax, int yMax, List<Point> result) {
        if (node == null) return;

        if (node.point.y > yMax) return;

        if (node.point.x >= xMin && node.point.x <= xMax) {
            result.add(node.point);
        }

        if (xMin <= node.xMid && node.left != null) {
            query3Sided(node.left, xMin, xMax, yMax, result);
        }

        if (xMax > node.xMid && node.right != null) {
            query3Sided(node.right, xMax, xMid, yMax, result);
        }
    }

    public static void main(String[] args) {
        List<Point> pts = new ArrayList<>();
        pts.add(new Point(2, 10));
        pts.add(new Point(3, 1));
        pts.add(new Point(5, 4));
        pts.add(new Point(7, 2));
        pts.add(new Point(8, 15));
        pts.add(new Point(11, 6));

        PSTNode root = buildPST(pts);

        System.out.println("Priority Search Tree constructed with 6 points.");
        System.out.println("Query range [x_min=4, x_max=10, y_max=8]:");

        List<Point> res = new ArrayList<>();
        query3Sided(root, 4, 10, 8, res);

        res.sort((a, b) -> {
            if (a.x != b.x) return Integer.compare(a.x, b.x);
            return Integer.compare(a.y, b.y);
        });

        for (Point p : res) {
            System.out.println("Found point: " + p);
        }
        System.out.println("Total points reported: " + res.size());
    }
}

Complexity, Correctness, and Invariants

The theoretical efficiency of Priority Search Trees stems from decoupling space complexity from range query dimensioning.

Variants, Pitfalls, and Optimizations

Common Variants

1. Max-Heap PST ($y \ge y_{min}$): Replaces the Min-Heap condition with a Max-Heap condition on $y$ to handle queries bounded below by $y_{min}$ ($[x_{min}, x_{max}] \times [y_{min}, +\infty]$).
2. Dynamic Priority Search Trees: Uses balanced binary search trees (such as Red-Black trees) as the underlying $x$-structure, enabling insertions and deletions in $O(\log N)$ time using tree rotations adapted to preserve min-heap properties.
3. Paired PSTs for 4-Sided Queries: Two Priority Search Trees (one min-heap, one max-heap) can be combined to answer 4-sided range queries $[x_{min}, x_{max}] \times [y_{min}, y_{max}]$ in $O(\log N + k)$ time using $O(N)$ space.

Practice Problems and Real-World Use

Priority Search Trees are widely used in computational geometry, spatial databases, and scheduling systems.