How to make STL's priority_queue fixed-size

Question

I am creating a simple game and I use std::priority_queue for giving commands to squads (every squad has a priority_queue<command>).

Every 20 seconds a bot analyses the situation and sends commands to the priority_queue.

How can I make the priority_queue fixed-size, for example, set the size to 10? The desired effect is that when the maximum is reached, if I add 2 new commands to the queue, 2 existing commands with the lowest priority are automatically removed.

Answer 1

Aryabhatta's answer of another question applies to this question.

You use a max-heap.

Say you have an N element heap (implemented as an array) which contains the N smallest elements seen so far.

When an element comes in you check against the max (O(1) time), and reject if it is greater.

Iteration mentioned by several earlier comments is unnecessary.

Answer 2

Wrap it in another class that will perform this operation for you. The Standard provides no such functionality on it's own.

Answer 3

It's sneaky, but you should be able to override functionality of std::priority_queue to do what you need. This seems to work in some of the tests I've done:

template<typename T>
class fixed_priority_queue : public std::priority_queue<T> 
{
  public:
    fixed_priority_queue(unsigned int size) : fixed_size(size) {}
    void push(const T& x) 
    { 
      // If we've reached capacity, find the FIRST smallest object and replace
      // it if 'x' is larger
      if(this->size() == fixed_size)
      {
        // 'c' is the container used by priority_queue and is a protected member.
        auto beg = c.begin(); auto end = c.end();
        auto min = std::min_element(beg, end);
        if(x > *min)
        {
            *min = x;
            // Re-make the heap, since we may have just invalidated it.
            std::make_heap(beg, end);
        }
      }
      // Otherwise just push the new item.
      else          
      {
        priority_queue::push(x);
      }
    }
  private:
    fixed_priority_queue() {} // Construct with size only.
    const unsigned int fixed_size;
    // Prevent heap allocation
    void * operator new   (size_t);
    void * operator new[] (size_t);
    void   operator delete   (void *);
    void   operator delete[] (void*);
};

What's happening here?

• Extend the std::priority_queue class
• Override the priority_queue::push() method, exchanging lowest item with new item
• Default constructor is private, no construction without size
• Restrict allocation on the heap, as STL containers have no virtual destructors.

To use:

const unsigned int LIMIT = 20;
fixed_priority_queue<int> fooQueue(LIMIT);

// Testing.
for(int i=0; i<40; i++)
  fooQueue.push(rand());
for(int i=0; i<LIMIT; i++)
{
  printf("%i\n", fooQueue.top());
  fooQueue.pop();
}

What's bad here?

• Well you can't safely create these queues on the heap, so big queues might be out of the question. 20 or so, as you mentioned should be fine on the stack anyway (depending on the object). I would probably avoid large queues because...
• I'm not sure of the performance hits here. priority_queue calls make_heap on the underlying container (std::vector by default). I'm not sure how often it's usually called, but we call it often if the queue is full. I think it may be called within priority_queue::push() aswell?
• Probably a heap of other things, so I welcome all constructive feedback and edits from readers :)

Hope this is useful, if not at least interesting.

Answer 4

The standard provides a set of primitive heap operations:

make_heap
sort_heap
push_heap
pop_heap

We can wrap it in a simple class which has a Command[10] or std::array<Command, 10> as its data member, or simply use the four functions above, in a lower-level fashion.

There are times when you want to keep the array at bay, not only as a priority queue. That's when these functions come in handy.

Answer 5

One idea is to create a min priority queue and use the size() method to only fill the priority queue to the required level. Something like this:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Compare {
    // priority queue is max heap by default, use compare
    // to make it minheap
    bool operator() (const int& a, const int& b) {
        return a>b;
    }
};

typedef priority_queue<int, vector<int>, Compare> pqSize;

void priorityQueueFixedSize(pqSize& pq, int size, vector<int>& vec) {
    for (int i=0;i<vec.size();i++) {
        if (pq.size() < size) {
            pq.push(vec[i]);
        } else {
            if (vec[i] > pq.top()) {
                pq.pop();
                pq.push(vec[i]);
            }
        }
    }
}

void printPQ(pqSize& pq) {
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

int main() {
    vector<int> vec(20,0);
    for (int i=0;i<vec.size();i++) {
        vec[i] = i;
    }
    pqSize pq;
    priorityQueueFixedSize(pq,10, vec);
    printPQ(pq);
}

This way only the maximum 10 elements will be held in the priority queue.

Answer 6

A bit tricky solution is not use std::priotity_queue, but std::array with size N+1, where only first N elements is a real queue. And instead of replacing element with lowest priority, you overwrite queue.back() with a new command. Than pop_queue(q.begin(), q.end()) adds new command to the queue.

Here is my code, that works:

int main() {
    std::array<int, 10> queue;
    queue.fill(500);
 
    for(int i = 0; i < 1000; i++)
    {
        queue.back() = rand() % 1000;
        pop_heap(queue.begin(), queue.end(), std::greater<int>());
        //print_queue(queue);
        assert(is_heap(queue.begin(), queue.end()-1, std::greater<int>()));
    }
}

The other thing is, whether your specification is what you really want. Do not forgot add an age into priority. If you don't, then after a million iteration you will have 10 element, with greatest priority. Does not matter when they were added to queue.