algorithm - 具有范围查询的优先级队列

Question

假设每个对象都具有这种形式：(key, priority)，即(0, 3), (5, 7)。假设给你两个数字，x 和 y。您将使用什么数据结构来返回键在 x 和 y 之间的最高优先级对象？我认为优先级队列可能是一个很好的解决方案，但我不知道如何修改它以返回给定范围内的最高优先级对象。

Answer 1

从二叉搜索树开始，为每个节点添加两个字段：优先级和（指向）子树中最高优先级节点的（指针）（有关如何执行此扩充的更多信息，请参见 CLRS 第 14 章）。

现在，要进行范围查询，请正常开始搜索，直到当前节点的键位于范围内。检查该节点，并使用以下过程的对称变体来识别包含范围内最高优先级节点的 O(log n) 候选者，即当前节点的左子树和右子树。以下过程适用于左子树。

如果根在范围内，则将其视为最高优先级，以及其右子树中的最高优先级节点（缓存在节点中）。继续左子树。如果根不在范围内，则继续右子树。

Answer 2

这个问题被称为 RMQ（范围最小/最大查询）。

在您的情况下使用的最佳数据结构是Segment Tree。

第一次做对是一个困难的结构，但继续尝试：这完全解决了你的问题。