c – 常量大小优先级队列 – 先插入或先删除？

概述我使用priority_queue来存储到目前为止在K-最近邻居搜索中找到的K个最近点.当我发现一个点比队列顶部的点更近时,我想d出顶部元素并推送新元素. if(point < pq.top()){ pq.pop(); pq.push(point);} 通常,首先d出然后插入是否更有效,或者首先插入然后d出更有效？ 如果使用std :: priority_queue作为优先级队列 我使用priority_queue来存储到目前为止在K-最近邻居搜索中找到的K个最近点.当我发现一个点比队列顶部的点更近时,我想d出顶部元素并推送新元素.

if(point < pq.top()){    pq.pop();    pq.push(point);}

通常,首先d出然后插入是否更有效,或者首先插入然后d出更有效？

解决方法 如果使用std :: priority_queue作为优先级队列类,则默认情况下标准容器类std :: vector用于其基础容器类.

通常,首先推送比首先推送效率低.

理由一

在priority_queue中推送一个元素将调用vector :: push_back,如果超过当前容量,它可能会重新分配底层缓冲区.

原因二

priority_queue::pop

When you pop an element from
priority_queue,it calls the
pop_heap algorithm to keep the heap
property of priority_queues,and then
calls the member function pop_back
of the underlying container object to
remove the element.

priority_queue::push

When you push an element to
priority_queue,it calls the member
function push_back of the underlying
container object,and then calls the
push_heap algorithm to keep the heap
property of priority_queues.

假设优先级队列中现在有N个元素.

如果先按下,则会调用push_heap算法两次,分别调整N 1和N 1个元素.

如果先d出,则调用push_heap算法两次,分别调整N和N个元素.

在旁边

如果您正在实现自己的优先级队列,这可能会节省性能.既然您已经使用top检查了值,我想知道您是否可以直接将元素与顶部交换而不调用push / pop,从而绕过堆调整算法.虽然可能不实用.

总结

以上是内存溢出为你收集整理的c – 常量大小优先级队列 – 先插入或先删除？全部内容，希望文章能够帮你解决c – 常量大小优先级队列 – 先插入或先删除？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。