如何在STLpriority_queue中进行高效的优先级更新？

发布于 2024-07-15 01:34:16 字数 782 浏览 10 评论 0原文

我有某个对象的priority_queue：

typedef priority_queue<Object> Queue;
Queue queue;

有时，其中一个对象的优先级可能会改变 - 我需要能够以有效的方式更新队列中该对象的优先级。目前我正在使用这种方法，它有效但似乎效率低下：

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

我以这种方式实现它是因为我当时很着急，这是我能做的最快的事情，我可以确定它会正常工作。但必须有比这更好的方法。我真正想要的是一种方法：

提取具有更改的优先级的实例，并插入具有新优先级值的新实例，
更新具有更改的优先级的实例，然后更新队列，以便它正确排序

什么是最好的方法来做到这一点？

原文

I have a priority_queue of some object:

typedef priority_queue<Object> Queue;
Queue queue;

From time to time, the priority of one of the objects may change - I need to be able to update the priority of that object in the queue in an efficient way. Currently I am using this method which works but seems inefficient:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

I implemented it this way because I was in kind of a hurry at the time and this was the quickest thing I could do that I could be sure it would work ok. There has to be a better way than this though. Really what I want is a way to either:

extract out the instance with the changed priority and insert a new one with the new priority value
update the instance with the changed priority and then update the queue so that it is correctly sorted

What is the best way to do this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

飘过的浮云 2024-07-22 01:34:16

我可以建议两种选择来解决问题，尽管两者都没有执行真正的更新。

每次您想要更新时，请使用 priority_queue 并推送元素。接受这样一个事实：队列中将有无用的条目。弹出顶部值时，检查它是否包含最新值。如果没有，请忽略它并弹出下一个。
通过这种方式，您可以延迟删除更新的元素，直到它到达顶部。我注意到实现 Dijkstra 算法的顶级程序员正在使用这种方法。
使用设置。它还经过排序，以便您能够在对数时间内提取最大元素。您还可以在再次插入之前删除过时的元素。因此仍然无法进行更新操作，但可以删除和重新插入。

似乎两种方法的复杂性是相同的。

回复收藏 0 原文

行至春深 2024-07-22 01:34:16

我认为你对标准优先级队列不走运，因为你无法获得底层的双端队列/向量/列表或其他东西。您需要实现自己的 - 这并不难。

回复收藏 0 原文

故人如初 2024-07-22 01:34:16

我实现了一个高性能可更新优先级队列，并在github上提供了它。

这就是您通常使用它的方式：

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

为了补充 Jarekczek 的答案，如果 set 和“带有无用条目的纯堆”方法确实具有相同的复杂性，则 stl::set code> 版本的执行速度通常比 stl::priority_queue 版本慢得多，因为它是用红黑树实现的，只能保证其深度低于 2*log_2(n_elements) 并且需要定期更新，而 stl::priority_queue 是尽可能纯粹且快速的二进制堆。这就是为什么在实现 Dijkstra 时通常使用它。

然而，当在少数基本节点上进行大量更新时，集合方法可能会更快。这也是使用我的库会给您带来最大改进的地方。

I have implemented a high-performance updatable priority queue and made it available on github.

This is how you would typically use it :

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

To complement Jarekczek's answer, if indeed both the set and "pure heap with useless entries" approaches have the same complexity, the stl::set version typically performs much slower than the stl::priority_queue version due to the fact that it is implemented with red-black trees that only guarantee their depth to be lower than 2*log_2(n_elements) and require regular updates, while stl::priority_queue is an as pure and fast binary heap as possible. This is why it is typically used when implementing Dijkstra.

The set approach may however be faster when making a lot of updates on few base nodes. This is also where using my library would bring you the most improvement.

回复收藏 0 原文