我有一个对象的priority_queue:
typedef priority_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
我是这样实现的,因为我当时有点匆忙,这是我能做的最快的事情,我可以确定它能正常工作.不过必须有比这更好的方法.真的我想要的是一种方式:
使用更改的优先级提取实例,并插入具有新优先级值的新实例
使用更改的优先级更新实例,然后更新队列以便正确排序
做这个的最好方式是什么？
我可以建议2个选择来解决问题,尽管它们都没有执行真正的更新.
priority_queue每次要更新它时都使用和push元素.接受您将在队列中包含无用条目的事实.弹出最高值时,检查它是否包含最新值.如果没有,请忽略它并弹出下一个.
这样,您可以延迟删除更新的元素,直到它到达顶部.我注意到这种方法被顶级程序员用来实现Dijkstra算法.
使用set.它也是排序的,因此您可以在对数时间内提取最大元素.您还可以在再次插入之前删除过时的元素.因此仍然无法进行更新操作,但删除和重新插入是可行的.
似乎两种方法的复杂性是相同的.
我认为你对标准优先级队列运气不好,因为你无法获得底层的deque/vector/list或其他什么.你需要实现自己的 - 它并不难.
使用STL(我知道)执行此操作的最直接方法是删除条目,更新其优先级,然后重新插入它.使用std :: priority_queue执行此操作非常慢,但是您可以使用std :: set执行相同的操作.不幸的是,当它在集合中时,你必须小心不要改变对象的优先级.
我已经实现了一个mutable_priority_queue类,它将std :: multimap(用于优先级到值映射)和std :: map(用于值到优先级映射)粘合在一起,它允许您插入/删除项目以及以对数方式更新现有值时间.您可以在此处获取代码以及如何使用它的示例
适当的数据结构称为"Fibonacci Heap".但是你需要自己实现它.插入/更新是O(1)ExtractMin是O(logn)
京公网安备 11010802040832号 | 京ICP备19059560号-6 