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

发布时间：2020-12-16 09:34:25 所属栏目：百科来源：网络整理

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

我使用priority_queue来存储到目前为止在K-最近邻居搜索中找到的K个最近点.当我发现一个点比队列顶部的点更近时,我想弹出顶部元素并推送新元素.

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

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

解决方法

如果使用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个元素.

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

在旁边

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!