How to Use the STL Priority Queue in C++

1. Use std::priority_queue to Declare a Priority Queue in C++
2. Use the Template Argument to Specify the Ordering Function in C++
3. Use the Custom Comparator to Specify the Element Ordering in C++

This article will demonstrate multiple methods about how to use the STL priority queue in C++.

Use std::priority_queue to Declare a Priority Queue in C++

The std::priority_queue class is a container adaptor that implements a queue from which the elements are read according to their priority. Note that priority_queue can utilize any sequence container internally for elements, and the user can pass the preferred one as the second template parameter. If the latter parameter is not specified, the vector container is used by default.

The elements of priority_queue are manipulated using the same functions as the queue container. The push member function inserts a new element into the queue and the top function to access the top element. These two functions are utilized in the printQueue function to output elements to the cout stream.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  for (int n : vec1) q1.push(n);

  printQueue(q1);

  return EXIT_SUCCESS;
}

Output:

8, 7, 6, 5, 3, 1,

Use the Template Argument to Specify the Ordering Function in C++

The priority for each element is determined using the compare function that the user can optionally specify. Otherwise, the descending order is chosen by default. We can construct the priority_queue from the previous example code in reverse ordering using the std::greater function object as the third template parameter. Notice that a new queue container is initialized using the range-based constructor.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  std::priority_queue<int, vector<int>, std::greater<>> q2(vec1.begin(),
                                                           vec1.end());
  printQueue(q2);

  return EXIT_SUCCESS;
}

Output:

1, 3, 5, 6, 7, 8,

Use the Custom Comparator to Specify the Element Ordering in C++

At first, we define a vector of strings used to initialize a priority_queue. Next, a lambda expression is defined to form the comparator function. The latter compares two strings by length. Now, we can declare a priority_queue object with three template parameters specifying the element type, underlying container type, and the comparator function, respectively. The range-based constructor is utilized to initialize the contents of the queue.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  vector vec2 = {"porro", "quisquam", "est", "qui", "dolorem", "ipsum", "quia"};
  auto compFunc = [](const string& s1, const string& s2) {
    return s1.length() < s2.length();
  };

  std::priority_queue<string, vector<string>, decltype(compFunc)> q3(
      vec2.begin(), vec2.end(), compFunc);

  printQueue(q3);

  return EXIT_SUCCESS;
}

Output:

quisquam, dolorem, ipsum, porro, quia, qui, est,