Priority Queue

I found the data structure called “Priority Queue” in <queue> libaray.

This is literally a queue that contains data based on the priority, which is similar with a heap.

Let’s say that we use a priority queue for integer data.

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

using namespace std;

int main() {

    priority_queue<int> q1;
    priority_queue<int, vector<int>, less<int>> q2;
    priority_queue<int, vector<int>, greater<int>> q3; 

    return 0;
}

We can say that q1 and q2 are the same structures.

When we declare priority_queue, we need the data type, structure and comparison operator as parameters.

If we specify only the type of data, which is int, then the structure becomes vector<int> and opertor is less<int>.

This gives more priority to bigger value by comparing in descending order.

If we want to make it in ascending order, we can put greater<int> to third parameter like in q3.

Now let’s see how the values are pushed and popped by exectuing below codes.

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

using namespace std;

int main() {

    priority_queue<int> q1;
    priority_queue<int, vector<int>, less<int>> q2;
    priority_queue<int, vector<int>, greater<int>> q3;

    vector<int> v = {3, 6, 1, 2, 0, 7};

    for (int i=0; i<v.size(); ++i) {
        q1.push(v[i]);
        q2.push(v[i]);
        q3.push(v[i]);
    }

    cout<<"q1: ";
    while(!q1.empty()) {
        cout<<q1.top()<<" ";
        q1.pop();
    }
    cout<<"\n";

    cout<<"q2: ";
    while(!q2.empty()) {
        cout<<q2.top()<<" ";
        q2.pop();
    }
    cout<<"\n";

    cout<<"q3: ";
    while(!q3.empty()) {
        cout<<q3.top()<<" ";
        q3.pop();
    }
    cout<<"\n";

    return 0;
}

We can see that if the operator is declared as descending order, the values are ordered from bigger to smaller and vice versa.

Another interesting thing is that originally we use front() to check the front value of a queue, but instead we should use top() for a priority queue.

This is because a priority queue is more similar with a heap than with a original queue.

And the time complexity is also bounded by that of a heap.

It takes $O(logN)$ to push or pop a value, so it can be useful for problems which should be approached with $O(NlogN)$ time complexity.

Categories