您可以使用平衡二叉树(例如红黑树)来存储排序后的索引,这应该比每次都对整个索引进行排序时更新速度更快。
使用 Java-ish 伪代码,这看起来像
Tree tree;
Node {
int priority;
incrementPriority() {
priority = priority + 1;
if(priority > tree.nextHighestNode(this)) {
tree.remove(this);
tree.add(this);
}
}
decrementPriority() {
priority = priority - 1;
if(priority < tree.nextLowestNode(this)) {
tree.remove(this);
tree.add(this);
}
}
}
如果更改节点的优先级意味着它位于无效的树位置(意味着它高于应该是下一个最高节点,或者低于应该是下一个最低节点),那么它会被移除并重新 -添加到树(负责重新平衡自身)。插入是 O(log(n)),但通常(当没有插入/删除时)更新优先级是一个恒定时间操作。
红黑树是平衡二叉树的通常实现方式,但也有替代方案,例如Tango 树可能更适合这里,因为它是在线实现。最大的问题是并发性 - 理想情况下,您希望能够使用某种 AtomicInteger 实现节点的优先级字段(允许原子增量和减量;相当多的语言都有这样的东西),这样你就不会了每次更改时都需要锁定字段,但是很难将优先级与相邻节点的优先级进行原子比较。
作为替代方案,您可以将所有内容存储在数组或链表中,并在它们的优先级发生变化时交换相邻元素 - 这样您就不需要每次都进行完整排序,这与平衡二叉树不同,其中删除和插入元素是 O(log(n)),交换两个相邻的数组/列表元素是常数时间。唯一的问题是使用数组添加一个全新的元素会很昂贵,因为您需要移动数组的所有元素;它也将是 O(n) 与列表,因为您需要遍历列表直到找到插入项目的正确位置,但这可能比数组更可取,因为您不需要移动任何相邻的元素(这将减少您需要执行的锁定量)。