哪种数据结构用于"动态"优先级排队？

Question

我正在寻找一种数据结构来支持一种高级优先级排队.这个想法如下.我需要按顺序处理多个项目,并且在任何给定的时间点我都知道下一个要做的"最佳"项目(基于某个度量标准).问题是,处理项目会更改其他几个项目的度量标准,因此静态队列不会起作用.

在我的问题中,我知道哪些项目需要更新其优先级,因此我正在寻找的数据结构应该有方法

• 入队(项目,优先权)
• 出队()
• requeue(item,new_priority)

理想情况下,我想在O(log n)时间内重新排队.有任何想法吗？

Answer 1

有一种算法的时间复杂度与您所需的类似，但如果您需要的话，它O(log n)仅以平均时间运行。在该算法中，您可以使用现有的优先级队列，而无需该requeue()功能。

假设图形中的节点与优先级队列中的元素之间存在连接。让优先级队列的元素还存储一个额外的位，称为ignore。修改后的算法dequeue运行如下：

1. 称呼dequeue()
2. 如果ignore元素中的位为 true，则返回 1，否则返回项目 id。

修改后的算法enqueue运行如下：

1. 调用入队（项目，优先级）
2. v一一 访问图中该项的邻居节点
   • ignore将队列中当前链接元素对应的位更改为 truev
   • 入队（v，new_priority（v））
   • v更改节点与新排队元素的连接。
   • num_ignore++
3. 如果忽略元素（ ）的数量num_ignore大于非忽略元素的数量，则重建优先级队列
   • dequeue所有元素，存储，然后再次enqueue仅非忽略元素

在此算法中，位的设置ignore需要恒定时间，因此您基本上会延迟O(log n)“重新排队”，直到累积O(n)忽略元素。然后将它们全部清除一次，这需要O(n log n). 因此，平均而言，每次“重新排队”需要O(log n)。