Free implementation of "bounded priority queue" in C++

Question

I'm looking for a free software implementation of the bounded priority queue abstraction in C++. Basically, I need a data structure that will behave just like std::priority_queue but will at all times hold the "best" n elements at most.

Example:

std::vector<int> items; // many many input items
bounded_priority_queue<int> smallest_items(5);
for(vector<int>::const_iterator it=items.begin(); it!=items.end(); it++) {
  smallest_items.push(*it);
}
// now smallest_items holds the 5 smallest integers from the input vector

Does anyone know of a good implementation of such thing? Any experience with it?

I think this is covered in http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm — Mark B, Mar 16 '11 at 18:13

score 1 · Accepted Answer · edited May 23 '17 at 11:43

I think that the algorithm discussed in this thread is probably what you are looking for. If you want to get a head start, you might want to consider building upon Boost's implementation d_ary_heap_indirect which is part of Boost.Graph (in d_ary_heap.hpp). If you do a good job with it, you might submit it to Boost. It could make a nice little addition, because such an implementation certainly has many uses.

score 0 · Answer 2 · answered Mar 16 '11 at 17:52

0

Why not use a std::vector with a functor/comparison function and std::sort() it into the correct order? The code is probably pretty trivial

answered Mar 16 '11 at 17:52

Jay

13,803
4
42
69

3

That could perform significantly worse than a heap in certain cases. – Mark B Mar 16 '11 at 18:12

Free implementation of "bounded priority queue" in C++

2 Answers2

Linked