Cho*_*Luo 53 c++ algorithm data-structures
有时在编程竞赛等过程中,我们需要一个简单的最小优先级队列的工作实现,使用reduce-key来实现Dijkstra算法等.我经常使用set <pair <key_value,ID >>和一个数组(映射ID - > key_value) )共同实现这一目标.
向集合添加元素需要O(log(N))时间.要从N个元素中构建优先级队列,我们只需将它们逐个添加到集合中.这总共需要O(N log(N))时间.
具有min key_value的元素只是集合的第一个元素.探测最小元素需要O(1)时间.删除它需要O(log(N))时间.
为了测试集合中是否有一些ID = k,我们首先在数组中查找其key_value = v_k,然后搜索集合中的元素(v_k,k).这需要O(log(N))时间.
要将某些ID = k的key_value从v_k更改为v_k',我们首先在数组中查找其key_value = v_k,然后搜索集合中的元素(v_k,k).接下来,我们从集合中删除该元素,然后将元素(v_k',k)插入集合中.然后我们也更新阵列.这需要O(log(N))时间.
虽然上述方法有效,但大多数教科书通常建议使用二进制堆来实现优先级队列,因为构建二进制堆的时间只是O(N).我听说在C++的STL中有一个使用二进制堆的内置优先级队列数据结构.但是,我不确定如何更新该数据结构的key_value.
在C++中使用最小优先级队列和密钥更新的最简单,最有效的方法是什么？
Chr*_*ica 43
好吧,正如Darren已经说过的那样,std::priority_queue没有办法降低元素的优先级,也没有删除除当前min之外的元素.但是默认std::priority_queue只是一个简单的容器适配器,std::vector它使用来自<algorithm>(std::push_heap,std::pop_heap和std::make_heap)的std堆函数.所以对于Dijkstra(你需要优先更新)我通常只是自己做这个并使用一个简单的std::vector.
然后推送就是O(log N)操作
vec.push_back(item);
std::push_heap(vec.begin(), vec.end());
当然,为了从N个元素中重新构造一个队列,我们不会使用这个O(log N)操作来推动它们(使整个事物O(Nlog N)),而只是将它们全部放入向量中,然后是一个简单的O (N)
std::make_heap(vec.begin(), vec.end());
min元素是一个简单的O(1)
vec.front();
pop是简单的O(log N)序列
std::pop_heap(vec.begin(), vec.end());
vec.pop_back();
到目前为止,这std::priority_queue通常是引擎盖下的内容.现在要更改项目的优先级,我们只需要更改它(但它可以包含在项目的类型中)并使序列再次成为有效的堆
std::make_heap(vec.begin(), vec.end());
我知道这是一个O(N)操作,但另一方面,这消除了使用额外的数据结构跟踪项目在堆中的位置的任何需要,或者(更糟糕的是)增加了项目类型.考虑到易用性,紧凑和线性内存使用std::vector(也影响运行时),以及我经常使用边缘相当少的图表,对对数优先级更新的性能损失实际上并不显着(无论如何,在顶点计数中是线性的).
在所有情况下,它可能不是最快的方式,但肯定是最简单的方法.
编辑:哦,因为标准库使用max-sheaps,你需要使用等价来>比较优先级(但是你从项目中得到它们),而不是默认的<运算符.
小智 39
虽然我的回答不会回答原来的问题,但我认为对于那些在尝试用C++/Java(像我自己)实现Dijkstra算法时遇到这个问题的人来说可能是有用的,这是由OP评论的,
priority_queue在C++(或PriorityQueueJava)中decrease-key,如前所述,不提供操作.在实现Dijkstra时使用这些类的一个很好的技巧是使用"延迟删除".Dijkstra算法的主循环从优先级队列中提取要处理的下一个节点,并分析其所有相邻节点,最终改变优先级队列中节点的最小路径的成本.decrease-key为了更新该节点的值,通常需要这一点.
诀窍根本不是改变它.相反,该节点的"新副本"(具有新的更好的成本)被添加到优先级队列中.具有较低的成本,该节点的新副本将在队列中的原始副本之前被提取,因此它将被更早地处理.
这种"延迟删除"的问题在于,最终从优先级队列中提取具有较高不良成本的节点的第二副本.但是,这将始终发生在第二个添加的副本之后,处理成本更高.因此, 当从优先级队列中提取下一个节点时,主Dijkstra循环必须做的第一件事是检查节点是否先前已被访问过(我们已经知道最短路径).正是在这个精确的时刻,我们将进行"懒惰删除",并且必须简单地忽略该元素.
此解决方案将在内存和时间上都有成本,因为优先级队列正在存储我们尚未删除的"死元素".但实际成本将非常小,编程此解决方案,恕我直言,比试图模拟丢失decrease-key操作的任何其他替代方案更容易.
Dar*_*rda 19
我不认为std::priority_queue该类允许decrease-key样式操作的有效实现.
我推出了自己的基于二进制堆的数据结构,支持这一点,基本上与您为std::set基于优先级的队列所描述的非常相似:
value存储的元素pair<value, ID>和映射的数组进行排序ID -> heap_index.在堆例程heapify_up, heapify_down等中,必须确保映射数组与元素的当前堆位置保持同步.这增加了一些额外的O(1)开销.O(N)根据此处描述的标准算法将阵列转换为堆. O(1).ID当前是否在堆中只需要O(1)在映射数组中查找.这也允许O(1)窥视对应于任何元素的元素ID.Decrease-key需要O(1)在映射数组中查找,然后通过O(log(N))更新堆heapify_up, heapify_down.O(log(N))就像从堆中弹出一个退出项目一样.因此渐近地,与std::set基于数据的结构相比,一些操作的运行时得到了改进.另一个重要的改进是二进制堆可以在阵列上实现,而二叉树是基于节点的容器.二进制堆的额外数据位置通常转换为改进的运行时.
这个实现的一些问题是:
ID.ID从零开始(否则映射数组的空间复杂性会爆炸!).如果您维护映射哈希表而不是映射数组,但可能会有更多的运行时开销,则可能会克服这些问题.对我来说,整数ID总是足够的.
希望这可以帮助.