Suppose each object has this form: (key, priority) i.e., (0, 3), (5, 7). Say you are given two numbers, x and y. What data structure would you use to return the highest-priority object whose key is between x and y? I think priority queue can be a good solution, but I have no idea how to modify it to return the highest-priority object in the given range.
2 Answers
Starting with a binary search tree, add two fields to each node: the priority, and (a pointer to) the highest-priority node in the subtree (see CLRS Chapter 14 for more on how to carry out this augmentation).
Now, to do a range query, start the search normally until the current node's key lies in the range. Examine that node and, using symmetric variants of the following procedure to identify O(log n) candidates that include the highest-priority node in range, the left and right subtrees of the current node. The following procedure is for the left subtree.
If the root is in range, consider it for highest priority, along with the highest-priority node in its right subtree (cached in the node). Continue with the left subtree. If the root is not in range, continue with the right subtree.
2 Comments
Анатолий
" to identify O(log n) candidates" What is guaranted that tree is balanced?
David Eisenstat
@Толя Read CLRS Chapter 14 -- this augmentation is of a type that can be restored in time O(1) after a rotation, so it works with a balanced binary search tree.
This problem is known as RMQ (Range Minimum/Maximum Query).
The best data structure to use in your case is Segment Tree.
It is a hard structure to get right the first time, but keep trying: this solves exactly your problem.
