6

我正在寻找一种数据结构来支持一种高级优先级队列。思路如下。我需要按顺序处理许多项目，并且在任何给定的时间点，我都知道下一步要做的“最佳”项目（基于某些指标）。问题是，处理一个项目会改变一些其他项目的指标，所以静态队列不能解决问题。

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

  • 入队（项目，优先级）
  • 出队（）
  • 重新排队（项目，新优先级）

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

4

4 回答 4

3

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

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

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

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

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

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

于 2012-12-28T17:31:37.320 回答
1

优先级队列正是为此而生。例如，您可以使用max-heap来实现它。

于 2012-12-28T09:31:41.130 回答
1

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

但是，如果我们假设在给定步骤中更新元素的数量是p堆的大多数典型实现，那么对于O(1)获取最大元素的值、O(log(n))对于双端队列和O(p * log(n))更新操作来说，这将变得更加复杂。我个人会选择二进制堆，因为它很容易实现并且可以满足您的要求。

于 2012-12-28T17:54:11.450 回答
0

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf描述了 increaseKey()、reduceKey() 和 remove() 操作。这会让你做你想做的事。我还没有弄清楚 C++ stdlib 实现是否支持它。

Further, the version: http://theboostcpplibraries.com/boost.heap seems to support update() for some subclasses, but I haven't found a full reference yet.

于 2015-10-10T01:19:56.597 回答