C++ priority_queue

• In C++, a priority_queue is a container adapter similar to a heap in that the first element is always the greatest

// basic usage

#include <queue>

std::priority_queue pq;

pq.push(10);
pq.push(20);
pq.push(1);
pq.push(5);

assert (pq.top() == 20);    pq.pop();
assert (pq.top() == 10);    pq.pop();
assert (pq.top() ==  5);    pq.pop();
assert (pq.top() ==  1);    pq.pop();

assert (pq.empty());

• The underlying container is normally a vector.
• However it can be any container which supports the following:
• random access iterators
• empty()
• size()
• front()
• push_back()
• pop_back()

// another example in which we specify both the container and the comparision function
// - by default the comparision function is less<T>

#include <queue>

struct cmp
{
    bool operator() (const int& l, const int& r) const
    {
        if (l < r)
            return true;
        return false;
    }
};

std::priority_queue<int, std::vector<int>, cmp> pq;

pq.push(10);
pq.push(20);
pq.push(1);
pq.push(5);

assert (pq.top() == 20);    pq.pop();
assert (pq.top() == 10);    pq.pop();
assert (pq.top() ==  5);    pq.pop();
assert (pq.top() ==  1);    pq.pop();

assert (pq.empty());