Bounded size priority queue

A priority queue in the STL is nothing more than a regular (maximum-) heap. It is essentially an adapter built on top of another container, usually a vector. Therefore, the offered priority queue can easily contain an arbitrary number of elements (so long as memory permits).

But what if we wanted to keep only the biggest N elements, and just have the queue dynamically throw away all other elements? I am sure you can imagine why such a behavior would be much desired: for instance, keeping the best N suggestions for a specific search term springs to mind. Unfortunately, the STL does not support such an adapter.

I believe the following assignment is a nice introductory interview question. Something to break the ice with, if you will:
Naturally, we’d want any solution to rely as heavily as possible on previously available code; How would you implement a bounded_priority_queue using only the given priority_queue from the STL?

At this point I would like to invite you, the readers, to take a moment and think of a solution for the provided specification. Keep in mind that the priority queue offered by the STL requires a Compare binary-function object (such as less) to be used for comparing the elements held within, and only supports a few relevant operations: push, pop and size.

The suggested solution is as follows:
Keeping a maximum heap of N elements, is exactly the same as holding a minimum heap and popping the minimal elements when the size is about to reach the limit (N) — asking for the maximal N elements is exactly the same as dropping the minimal elements until there are N elements left. We are able to convert a maximum heap to a minimum heap by altering the Compare function object mentioned above. More specifically, all we have to do is swap its two arguments.

I actually bumped into a need for such an implementation in my normal course of work. As Googling for an answer did not provide a solution, I thought posting one could be beneficial to others. Therefore, a nearly complete C++ solution is hereby provided:

#include <queue>
#include <stdexcept>
#include <algorithm>

template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type> 
         > class bounded_priority_queue {
    public:
        typedef T value_type;
        typedef std::size_t size_type;

        explicit bounded_priority_queue (const size_type& maxsize) 
         : maxsize_(maxsize) 
        {
            if (maxsize_ < 1)
                throw std::runtime_error("bpqueue maxsize<1");
        }

        void push (const value_type& val) {
            queue_.push(val);
            if (queue_.size() > maxsize_)
                queue_.pop();
        }

        std::priority_queue<T, Container, Compare> pop_all () {
            std::priority_queue<T, Compare, Container> result;

            bounded_priority_queue tmp(*this);
            while (!tmp.queue_.empty()) {
                result.push(tmp.queue_.top());
                tmp.queue_.pop();
            }

            std::swap(this->queue_, tmp.queue_); // specialized ptr swap
            return result; // return value optimization
        }

    private:
        struct reversed_compare : Compare {
            // notice that all four versions are required
            // so that no new restrictions are created:
            // (you might even want mixed const params..)

            bool operator() (const T& l, const T &r) {
                return Compare::operator()(r, l);
            }

            bool operator() (const T& l, const T& r) const {
                return Compare::operator()(r, l);
            }

            bool operator() (T& l, T& r) {
                return Compare::operator()(r, l);
            }

            bool operator() (T& l, T& r) const {
                return Compare::operator()(r, l);
            }
        };

        std::priority_queue<T, Container, reversed_compare> queue_;
        size_type maxsize_; // not const to stay assignable
};

Note that the interface for such a class is tricky – there is no good way of defining the top() functionality, as a maximum heap (with the reversed comparison, mind you) will not let you access the minimal member. It will only give access to the maximal one.
The solution I have suggested here works around this issue by providing only a way for retrieving all elements altogether, through pop_all. I would greatly appreciate any feedback on this matter.

Another interesting property of the pop_all implementation offered here is that it provides a strong exception guarantee – in the case of an exception during the copying of the elements, it will leave the original queue untouched. This is also achieved through the invocation of the swap algorithm, which should have a (no-throw) pointer-swapping specialization for the underlying vector type.
This is a very important characteristic, and it comes with a cost of an extra copy operation.

One more issue worth taking note of is that the provided pop_all implementation supports return value optimization. But that is a topic for another post.

4 thoughts on “Bounded size priority queue

  1. add an explicit to your one-integer-argument constructor.


    explicit bounded_priority_queue (const size_type& maxsize)

  2. In your push() implementation you do not check that pop()-ed elemnt has lower priority than the new element being inserted. Probably you should push() first and pop() later? In any case it will have to heapify twice..

    1. That is right: the effecient thing to do would be to compare top() with the new element and then continue according to that result.
      I shall update the sourcecode asap.

      Thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>