用于“动态”优先级队列的数据结构是什么？

Question

我正在寻找一个数据结构来支持一种高级优先级排队。其想法如下。我需要依次处理许多项，并且在任何给定的时间点上，我都知道下一步要做的“最佳”项(基于某种度量)。问题是，处理一个项会改变其他几个项的度量标准，所以静态队列不起作用。

在我的问题中，我知道哪些项目需要更新它们的优先级，所以我正在寻找的数据结构应该有方法。

• 队列(项、优先级)
• 排程()
• 请求(项目，new_priority)

理想情况下，我希望在O(log )时间内请求。有什么想法吗？

Answer 1

有一个时间复杂度类似于您所需的算法，但是它只在O(log n)上运行平均时间，如果它是您所需要的。在此算法中，您可以使用现有的优先级队列而不使用requeue()函数。

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

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

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

1. 呼叫队列(项目、优先级)
2. 访问图中项的邻居节点v，逐个访问
   • 对于队列中的当前链接元素，将ignore位更改为true，对应于v
   • 排队(v，new_priority(v))
   • 更改节点v到新的排队元素的连接。
   • num_ignore++

​

1. 如果忽略元素(num_ignore)的数量大于非忽略元素的数量，则重新生成优先级队列。
   • dequeue所有元素，然后再存储，然后只enqueue非忽略元素。

​

在此算法中，ignore位的设置需要恒定的时间，因此基本上将O(log n)的“请求”延迟到积累O(n)忽略元素为止。然后将它们全部清除一次，这就需要O(n log n)。因此，平均而言，每个"requeue“都采用O(log n)。

Answer 2

您无法达到所要求的复杂性，因为在更新元素时，复杂性还应取决于更新元素的数量。

但是，如果我们假设给定步骤上更新的元素的数量是p，堆的大多数典型实现都会对O(1)复杂性产生影响，以获得max-元素的值，O(log(n))表示deque，O(p * log(n))用于更新操作。我个人会选择二进制堆，因为它很容易实现，并且可以满足您的要求。

Answer 3

优先级队列正是用于这个目的的。例如，您可以使用最大堆来实现它。