2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Is the best way to do so to keep a heap at each internal node? $\endgroup$ Jan 15 at 22:24
  • $\begingroup$ @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). $\endgroup$
    – D.W.
    Jan 15 at 23:31
  • $\begingroup$ 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. $\endgroup$ Jan 16 at 0:14
  • $\begingroup$ @DavisYoshida, deletion doesn't require linear time; deletion is just as fast as search. See edited answer. $\endgroup$
    – D.W.
    Jan 16 at 0:44
  • $\begingroup$ Ah gotcha. Thanks! $\endgroup$ Jan 16 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.