Multiple insertions and deletion in priority_queue

Question

Problem

In my algorithm I have to implement a "Ordered queue" (I choose this name to distinguish the idea in my mind from existing implementations). I have to insert some values into a queue where the value represents the order in the queue, and then I have to digest the queue following the order. I have the feeling that the best data structure for what I need to do is std::priority_queue, but I have some concerns about the efficiency of my program, in particular due to:

• Interface which does not provide methods for insertions/deletions of multiple elements
• (Possibly) Internal design of the class and its algorithms

From the documentation, both priority_queue::push and priority_queue::pop internally call std::push_heap and std::pop_heap, which both have complexity O(log(N)). I think it is very inefficient to insert/delete one element at a time, resorting the underlying container at every call.

Why is it implemented in this way? Maybe when you call std::push_heap and std::pop_heap in a sequence the underlying heap structure is in the optimal case and the complexity is reduced with respect to O(log(N))?

Otherwise, is there a best data structure which fits my needs that I have not considered? I thought also std::forward_list could fulfil my needs on deletion (through forward_list::pop_front), but I fear that the insertion becomes too expensive as I should find the iterator for the correct place to insert, which should be O(N).

I would prefer not to rely on any external library (Boost included) because the project must be lightweight and dependency-free.

Implementation

The program is equivalent to:

struct MyType{
    double when;
    int who;
    MyType(double t, double i) : when(t), who(i) {};
    bool operator<(const MyType & other) const{ return when < other.when; }
};

using OrderedQueue = priority_queue<MyType,std::vector<MyType>,std::less<MyType>>;

const double TMax = 1e9; // some BIG stopping condition

double some_time(){/*routine to generate the time*/ return TMax * rand(); }

int some_number(){/*routine to generate the number*/ return 100 * rand(); }

void populate(OrderedQueue & q){
    unsigned Ni = 10; // number of insertions: it is not fixed in the real program
    for (auto i = 0; i < Ni; ++i){
        q.emplace(some_time(), some_number());
    }
}

void use_MyType(MyType m){/*routine that uses the top value*/ return; }

void remove(double t, OrderedQueue & q){
    while(q.top().when < t){
        use_MyType(q.top());
        q.pop();
    }
}

int main(){
    double t = 0;
    OrderedQueue q;
    while(t < TMax){
        populate(q);
        remove(t, q);
        t += 1;
    }
}

I am particularly interested in the efficiency of populate() and remove() because the loop when they are called has very many iterations.

Answer 1

std::priority_queue is an adaptor for a heap structure. Given your requirements of consuming elements in order one by one, a heap is the most efficient structure.

Heap insertions are worst case O(log(N)), but are on average O(1). This is faster than e.g. a binary tree (std::map) insertion, which is always O(log(N)). Similarly, removing the top element from a heap is worst case O(log(N)), but on average much faster since a heap is partially sorted.

With that said, the effects of branch prediction and caching in modern computers cannot be neglected. The best way to answer a performance question is to benchmark it with your actual data and a representative number of elements. I would suggest to benchmark using these 3 queue structures:

• std::priority_queue<MyType, std::vector<MyType>>
• std::priority_queue<MyType, std::deque<MyType>>
• std::map<MyType>

std::deque as the backing store may offer improved pop_front performance, at the expense of slower random access. So it should be benchmarked.

I would disregard std::list (std::forward_list) at this point - inserting into a linked list at the right place is O(N), plus a linked list isn't cache-friendly, so is definitely going to be a much slower solution.

For more details on Heap vs Binary Tree performance, see this related question.

---

To address your concerns:

Interface which does not provide methods for insertions/deletions of multiple elements

Inserting an element into a heap involves appending the element at the end and "repairing" the heap structure. This is what the std::push_heap algorithm does. It is entirely feasible to implement an algorithm to insert multiple elements this way and/or simply invoke std::make_heap after appending multiple elements to repair the entire heap.

Removing multiple elements from a heap isn't possible, since a heap is only sorted with respect to the first (top) element. After removing it, the heap structure needs to be adjusted to find the next top element. This is what the std::pop_heap algorithm does.

Internal design of the class and its algorithms

std::priority_queue is just an adapter around heap algorithms. It's a convenience class that wraps a sequential container and invokes heap algorithms on it. You don't have to use it, you can use std::vector, std::push_heap and std::pop_heap with exact same results (though the code might be less readable and more error-prone).