Constant size priority queue - Insert first or delete first?

Question

I am using a priority_queue to store the K closest points found so far in a K-nearest-neighbor search. When I find a point closer than the point at the top of the queue, I want to pop the top element and push the new one.

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

Generally, is it more efficient to pop first and then insert, or is it more efficient to insert first and then pop?

Answer 1

If you are using std::priority_queue as your priority queue class, the standard container class std::vector is used for its underlying container class, by default.

Generally, it is less efficient to push first than pop first.

Reason one

Pushing an element in priority_queue will envoke vector::push_back which can potentially reallocate the underlying buffer if it exceeds it current capacity.

Reason two

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.

Assume there are now N elements in priority queue.

If you push first, the algorithm push_heap is called two times, to adjust N+1 and N+1 elements, respectively.

If you pop first, the algorithm push_heap is called two times, to adjust N and N elements, respectively.

Aside

If you're implementing your own priority queue, this is probably a performance-saver. Since you already check the value with the top, I'm wondering if you can directly swap the element with the top without invoking the push/pop thus bypassing the heap adjusting algorithm. May not be practical though.