Skip to content

[C++] Note of priority_queue of STL

Last Updated on 2022-07-19 by Clay

priority_queue is a queue container provided in the C++ Standard Template Library (STL), which returns the element with the highest priority first.

In the general case of storing INT data, the priority of elements is sorted from large to small. Of course we can change the priority definition of priority_queue.

How to use priority_queue

The following is a simplest sample code

  • push(): Push element into queue.
  • top(): Get the highest priority element
  • pop(): Pop (delete) the highest priority element
#include <iostream>
#include <queue>
using namespace std;


int main() {
    // Init
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(5);
    pq.push(1);
    pq.push(6);

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

9
6
5
4
1


As you can see, the elements we randomly push into the queue have been sorted in descending order; it means that the larger the value, the higher the priority.


Change the priority rule

The smaller the value, the higher the priority

#include <iostream>
#include <queue>
using namespace std;


int main() {
    // Init
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(4);
    pq.push(9);
    pq.push(5);
    pq.push(1);
    pq.push(6);

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

1
4
5
6
9


This is the most common changes, we can do it directly with greater<int>.


Customize priority rule

If we want:

  • The even numbers have higher priority
  • The smaller number have higher priority

We can construct our own priority rules in the following way:

#include <iostream>
#include <queue>
using namespace std;


template <typename T>
class cmp {
    public: 
        bool operator()(T a, T b) {
            if (a % 2 == 1 && b % 2 == 0) {
                return true;
            }
            else if (a % 2 == 0 && b % 2 ==1) {
                return false;
            }
            else {
                return a > b;
            }
        }
};

int main() {
    // Init
    
    vector<int> v({1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
    priority_queue<int, vector<int>, cmp<int>> pq(v.begin(), v.end());

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

2
4
6
8
10
1
3
5
7
9


To make the demo more clear, I've added some numbers. And for example use vector<int> container to initialize priority_queue<int>.

References

Read More

Tags:

Leave a Reply