首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >提取priority_queue的最后一个元素

问提取priority_queue的最后一个元素
EN

Stack Overflow用户
提问于 2016-05-31 10:19:09
回答 1查看 2.7K关注 0票数 3

我使用一个std::priority_queue来编写一个算法来计算三维网格上数据集的距离函数。初始化队列后,我想将最后一个元素存储在一个单独的变量中,就像使用std::queue.back()一样,但是当然,优先级队列是不可能的,所以我的工作如下:

代码语言:javascript
复制
CellQueue q; //this is the actual priority_queue

//...
//initialization
//...

Cell* last = 0;
CellQueue dummy(q);
while (!dummy.empty()) {
    last = dummy.top();
    dummy.pop();
}

当然有更好的方法来解决这个问题,所以如果有人能给我看的话,我会很高兴的。

谢谢,

费德里科

编辑

@Sam @Dietmar计算距离函数(DF)的算法是这样工作的:在priority_queue中填充至少包含数据集一个点的网格单元格,然后按距离(这一步为零)按递增顺序排序。然后,对于队列的每个元素,访问邻居,并为每个邻居计算相对于其父元素的距离。现在,出于效率原因,我只想在数据集周围的一个窄带上计算DF。因此,为了停止这个过程后,访问了第三环邻里,我必须跟踪当前环的最后一个元素。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-05-31 10:38:33

“显而易见”的方法是与priority_queue一起存储最后一个(最小)元素的副本。跟踪这一点的额外工作与添加到优先级队列中的元素数量成正比,而您的解决方法是调用队列时队列大小的N个log(N),所以请选择。

无论何时pop,根据定义,只有当pop导致队列为空时,才能删除最后一个值,因此不需要担心更新pop上的任何内容。

每当您push到优先级队列时,将正在推送的值与当前的最小值进行比较,并在必要时替换它。emplace也是如此。

如果您想成为真正的花花公子,您可以通过编写您自己的容器适配器priority_queue_that_additionally_accesses_the_min_value来展示这一点。或者更短的名字。

如果您需要访问实际的元素,而不是它的副本,那么您就会遇到一个问题,即priority_queue本身将在您不查看的情况下在内部移动,因此不能只将指针保持在最小值。将元素封装在智能指针中可能会处理这个问题,当然,您需要为priority_queue提供一个比较器来判断智能指针。

最后,出现了“双结束优先级队列”.这将允许您有效地移除两端,而不是有效地从一端移除和检查两者。它不是在标准C++中,而是查找必要的结构和算法并自己实现,或者搜索“双端优先级队列”或"min/max堆“的C++实现。我自己从来没有使用过这种结构,所以我不会推荐具体的结构。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/37542974

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档