c++ - 恒定大小优先级队列 - 先插入还是先删除？

Question

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

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

一般来说，是先弹出再插入效率更高，还是先插入再弹出效率更高？

Answer 1

如果您使用 std::priority_queue 作为您的优先级队列类，标准容器类 std::vector 默认用于其底层容器类。

一般来说，先push效率不如先pop

原因一

将元素推送到 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，算法push_heap会被调用两次，调整N+1和N+1 元素，分别。

如果你先pop，算法push_heap会被调用两次，调整N和N元素, 分别。

放在一边

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