# Data structure for finding lowest element in range

Consider the following setting: There are tasks $$T = \{T_i\}_{i=1}^n$$ with priorities $$p_i$$, and locations $$x_i \in \mathbb{R}^2$$. Given a location $$y \in \mathbb{R}^2$$, I would like to find and pop the task with the highest $$p_i$$ in an $$L_\infty$$ ball of radius $$r$$ centered at $$y$$. What are some data structures that might make this more efficient?

One could use a ball tree to get efficient range queries, but then you have to iterate over all the tasks in range since they won't be sorted by priority. You could also maintain a sorted list of tasks, but then you might need to iterate over all of them if no tasks are in range of the query.

A plausible data structure might be a quadtree, where you augment each internal node with the priority of the highest-priority task contained within that region. This will let you do a best-first search, i.e., search first in regions that contain high-priority tasks, and avoid recursing into any region whose highest-priority task is of a lower priority than the best task found so far.

To elaborate a bit more, if $$x$$ is a tree node, let $$p(x)$$ denote the priority field associated with $$x$$ (i.e., the priority of the highest-priority task in the region associated with $$x$$). Note that $$x$$ has four children, let's call them $$y_1,\dots,y_4$$. Suppose we discover that the highest-priority task is under $$x$$, and we want to pop (delete) that task. Then this task must be under one of $$y_1,\dots,y_4$$, say $$y_i$$. Now we recursively pop (delete) that task from $$y_i$$, update $$p(y_i)$$, and then we can update $$p(x)$$ using the relation

$$p(x) = \max(p(y_1),\dots,p(y_4)).$$

Thus updating $$p(x)$$ can be done in $$O(1)$$ time. In the end, we do one update per node along the path from the root to the highest-priority task. This means that the cost to update all of the priority fields in the tree is at most the cost to search the tree to find the highest-priority task.

• Is the best way to do so to keep a heap at each internal node? Jan 15 at 22:24
• @DavisYoshida, there is no need for a heap at each internal node, just a single field that contains the value of the highest priority of all tasks underneath it (this can be computed bottom-up in linear time, and when you delete entries, it is easy to update it).
– D.W.
Jan 15 at 23:31
• I'd rather do better than linear time on deletion. In case it wasn't clear, the fundamental operation isn't just to find the minimum, but also delete it. Jan 16 at 0:14
• @DavisYoshida, deletion doesn't require linear time; deletion is just as fast as search. See edited answer.
– D.W.
Jan 16 at 0:44
• Ah gotcha. Thanks! Jan 16 at 7:53