C++ Priority Queues

A priority queue works in much the same way as a queue, which we covered in the previous lesson. There is one key difference: when we insert an object into a priority queue, it is not necessarily inserted into the back of the queue.

Rather, its insertion point is determined by its priority, with higher-priority objects being inserted closer to the front of the queue.

We cover how priority works, and how to customize it, later in the lesson. For now, let's see a simple example of creating a priority queue using std::priority_queue

std::priority_queue

The C++ standard library’s implementation of a priority queue is std::priority_queue. It’s available to us after we #include the <queue> header.

It is a template class that has 3 template parameters:

1. The type of data we’re storing in the queue
2. The type of underlying container we want to use
3. A comparison function for determining the priority of objects

The second and third parameters are optional, and we’ll cover them later. For now, let's see how we can create a simple priority queue of integers:

1#include <queue>
2
3int main() {
4  std::priority_queue<int> Numbers;
5}
6

The queue class does not have a constructor that lets us provide a list of initial values, but we can construct a priority queue from an iterator pair.

The iterator pair specifies a start and end for a range of values we want our priority queue to be initialized with:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{
7      Source.begin(), Source.end()};
8}
9

We can also construct a priority queue by copying another priority queue.

1#include <queue>
2
3int main() {
4  std::priority_queue<int> Numbers;
5  std::priority_queue<int> Copy{Numbers};
6}
7

When creating a queue from another queue, we can omit the template parameter. This will let the compiler infer it, using Class Template Argument Deduction (CTAD):

1#include <queue>
2
3int main() {
4  std::priority_queue<int> Numbers;
5  std::priority_queue Copy{Numbers};
6}
7

In the next sections, we’ll see how we can construct a priority queue from another container, or how we can push a collection of objects to the queue at once.

Container Adaptors - Set the std::priority_queue Container Type

The std::priority_queue class is a container adaptor. This means it does not manage the storage of its objects - rather, it defers that to another container class. std::priority_queue then interacts with the underlying container, to provide us with an API that acts like a priority queue.

By default, the container underlying std::priority_queue is a std::vector.

We can specify the underlying container by passing it as the second template parameter when creating our priority queue. As such, we could replicate the default behavior like this:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::priority_queue<int, std::vector<int>>
6      Numbers;
7

In this example, we set the underlying container to a std::deque instead of a std::vector. We cover std::deque (a double-ended queue) later in this chapter.

1#include <deque>
2#include <queue>
3
4int main() {
5  std::priority_queue<int, std::deque<int>>
6      Numbers;
7}
8

To maintain the priority ordering behavior, std::priority_queue adaptor needs random access to its elements, using the [], so we need to use a container that supports this.

In addition, the container needs to have the following methods:

• push_back() - adds an object to the end of the container
• pop_back() - removes the object at the end of the container
• front() - returns a reference to the object at the front of the container

Beyond implementing these methods, we’d preferably want the underlying container to be set up such that it can execute them efficiently. This is not enforced by the compiler, but if we want our priority queue to be performant, we should ensure the underlying container is performant when it comes to these functions.

Both std::vector and std::deque meet all these requirements, but we’re not restricted to using the standard library containers. Any class that meets the requirements can be used.

Initializing a Priority Queue from a Container

We can initialize a queue using a collection of the queue’s underlying type. Given the default underlying type is a std::vector, if we don’t change that, we can initialize our priority queue directly from a vector.

Note, there is not currently a dedicated constructor for this, but there is one that accepts an optional comparison function as the first argument, and an optional container as the second.

We’ll introduce custom comparers later in this lesson. For now, we don’t want to provide a custom compare, so we can pass {} as the first argument, and the vector as our second:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{{}, Source};
7}
8

If we no longer need the container from which we’re creating our priority queue, we can move it to our queue rather than performing a slower, unnecessary copy:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{
7      {}, std::move(Source)};
8}
9

We cover copy semantics, move semantics, and rvalue references in more detail in these lessons:

Copy Semantics, Elision, and RVO

Learn how to implement copy semantics in C++, and take advantage of copy elision and return value optimization (RVO)

Move Semantics, std::move and rvalues

Learn how to implement move semantics in C++, the difference between lvalues and rvalues, and what std::move really does.

Accessing Objects in our Priority Queue

Given the intended use of a priority queue, we should typically only be accessing elements at the front of it. If we need to access other elements, a queue is unlikely to be the correct data structure for our task.

The two methods we use for working with the front (or the “top”) of our priority queues are top and pop.

top()

The top method returns a reference to the object that is currently at the top of the queue, ie the object with the highest priority:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The top of the queue is "
11            << Numbers.top();
12}
13

1The top of the queue is 3
2

pop()

We use pop to remove the item at the top of the queue:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The top of the queue is "
11            << Numbers.top();
12
13  Numbers.pop();
14
15  std::cout << "\nThe top of the queue is now "
16            << Numbers.top();
17}
18

1The top of the queue is 3
2The top of the queue is now 2
3

Customizing the Priority Order

To customize the priority of objects in our queue, we pass a comparison function as the first argument to our constructor.

The comparison function will receive two objects as parameters and should return true if the first parameter has a lower priority than the second.

For example, if we want our queue of numbers to prioritize lower numbers, our comparison function might look like this:

1auto Comparer{
2    [](int x, int y) { return x > y; }};
3

When creating our queue, we need to pass the type of our comparison function as the third template parameter. Here, we ask the compiler to work it out, by passing our comparison function to decltype:

1using queue = std::priority_queue<
2    int,
3    std::vector<int>,
4    decltype(Comparer)>;
5

We can be explicit using std::function (from <functional>) instead of decltype:

1using queue = std::priority_queue<
2    int,
3    std::vector<int>,
4    std::function<bool(int, int)>>;
5

We cover std::function, and other functional helpers in a dedicated lesson:

C++ Standard Library Function Helpers

An introduction to a collection of standard library utilities that can help us when working with first class functions

Finally, when constructing our queue, we need to pass the comparison function into an appropriate constructor.

As of C++23, there are 19 different std::priority_queue constructors and 15 of them allow us to pass a comparison function.

We can see all the options in our IDE, but the following example uses the simplest, where we pass the comparer as the only argument:

1auto Comparer{
2    [](int x, int y) { return x > y; }};
3
4using queue = std::priority_queue<
5    int,
6    std::vector<int>,
7    std::function<bool(int, int)>>;
8
9queue Numbers{Comparer};
10

Here is a complete working example:

1#include <functional>
2#include <iostream>
3#include <queue>
4#include <vector>
5
6int main() {
7  std::vector<int> Source{1, 2, 3};
8
9  auto Comparer{
10      [](int x, int y) { return x > y; }};
11
12  using queue = std::priority_queue<
13      int, std::vector<int>,
14      std::function<bool(int, int)>>;
15
16  queue Numbers{Comparer, std::move(Source)};
17
18  std::cout << "The top of the queue is "
19            << Numbers.top();
20
21  Numbers.pop();
22
23  std::cout << "\nThe top of the queue is now "
24            << Numbers.top();
25}
26

1The top of the queue is 1
2The top of the queue is now 2
3

Adding Objects to the Queue

Similar to the regular std::queue, we have two ways to insert objects into our priority queue: we can either emplace them or push them.

emplace()

The emplace method will construct our object directly into the queue’s memory, which is preferred if the object doesn’t yet exist. Constructing an object in place is usually faster than constructing it elsewhere, and then moving or copying it.

The emplace method passes any arguments along to the constructor of the type stored in our priority queue:

1#include <iostream>
2#include <queue>
3
4int main() {
5  std::priority_queue<int> Nums;
6  Nums.emplace(10);
7
8  std::cout << Nums.top()
9            << " is at the top of the queue";
10}
11

110 is at the top of the queue
2

push()

If our object already exists, we can use the priority queue’s push method to copy or move it into our container:

1#include <iostream>
2#include <queue>
3
4int main() {
5  std::priority_queue<int> Nums;
6
7  int x{10};
8  int y{20};
9
10  // Copy
11  Nums.push(x); 
12
13  // Move
14  Nums.push(std::move(y));
15
16  std::cout << "We have " << Nums.size()
17            << " items in the queue";
18}
19

1We have 2 items in the queue
2

push_range()

Note: this is a C++23 feature, and is not yet supported by all compilers

Since C++23, we can now push a range into a priority queue.

Ranges were introduced in C++20, and we cover them in detail in our later chapters on algorithms. For now, the key point is that most of the sequential containers we work with will be a valid range, and can be passed to the push_range method.

Pushing a range into a priority queue looks like this:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::priority_queue<int> Nums;
7  std::vector Range{1, 2, 3};
8
9  Nums.push_range(Range);
10
11  std::cout << "We have " << Nums.size()
12            << " items in the queue";
13}
14

1We have 3 items in the queue
2

Checking the Priority Queue Size

The priority_queue class has two more useful functions:

size()

The size method returns an integer representing how many objects are in the queue:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The queue's size is "
11            << Numbers.size(); 
12
13  Numbers.pop();
14
15  std::cout << "\nThe size is now "
16            << Numbers.size(); 
17}
18

1The queue's size is 3
2The size is now 2
3

empty()

If we only care whether the object is empty (ie, size() == 0) we can use the dedicated empty() method:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::priority_queue<int> Numbers;
7  Numbers.emplace(5);
8
9  std::cout << "The queue "
10            << (Numbers.empty() ? "is" 
11                                : "is not")
12            << " empty\n";
13
14  Numbers.pop();
15
16  std::cout << "Now the queue "
17            << (Numbers.empty() ? "is" 
18                                : "is not")
19            << " empty";
20}
21

1The queue is not empty
2Now the queue is empty
3

Typical Priority Queue Usage

The typical approach for consuming a priority queue uses a while loop that continues whilst Queue.empty() is false. Within the body of the loop, we access the front() object, perform the required operations, and then pop() it off.

It might look something like this:

1#include <iostream>
2#include <queue>
3
4class Character {
5 public:
6  Character(std::string Name, int Level)
7      : Name{Name}, Level{Level} {}
8  std::string Name;
9  int Level;
10};
11
12int main() {
13  auto compare{[](Character& x, Character& y) {
14    return x.Level < y.Level;
15  }};
16
17  using QueueType = std::priority_queue<
18      Character, std::vector<Character>,
19      decltype(compare)>;
20
21  QueueType Q{compare};
22
23  Q.emplace("Aragorn", 40);
24  Q.emplace("Gandalf", 50);
25  Q.emplace("Bilbo", 20);
26  Q.emplace("Frodo", 30);
27
28  int SpaceInParty{3};
29
30  while (SpaceInParty && !Q.empty()) {
31    std::cout << "Adding " << Q.top().Name
32              << " (" << Q.top().Level
33              << ") to the party\n";
34    Q.pop();
35    --SpaceInParty;
36  }
37
38  std::cout << Q.size()
39            << " Character is still in queue";
40}
41

1Adding Gandalf (50) to the party
2Adding Aragorn (40) to the party
3Adding Frodo (30) to the party
41 Character is still in queue
5

Reprioritization / Dynamic Priorities in std::priority_queue

The standard library’s implementation of a priority queue does not support reprioritization or dynamic priority of objects that are already in the queue. The priority of each object is calculated only one time: when it is first inserted into the queue.

std::priority_queue does not give us a way to change the comparison function after our queue is created. Additionally, if we change an element in our queue in a way that would affect its prioritization, the object is going to remain in its original position, leaving our queue inaccurate.

Below, we prioritize our characters by highest Health. After modifying our top Character, it remains at the top of the queue, even though it no longer has the highest Health:

1#include <iostream>
2#include <queue>
3
4class Character {
5 public:
6  Character(std::string Name, int Health)
7      : Name{Name}, Health{Health} {}
8  std::string Name;
9  int Health;
10};
11
12int main() {
13  auto compare{[](Character* x, Character* y) {
14    return x->Health < y->Health;
15  }};
16
17  using QueueType = std::priority_queue<
18      Character*, std::vector<Character*>,
19      decltype(compare)>;
20
21  QueueType Q{compare};
22
23  Character Legolas{"Legolas", 100};
24  Character Gandalf{"Gandalf", 50};
25
26  Q.push(&Legolas);
27  Q.push(&Gandalf);
28
29  std::cout
30      << "The highest priority character is "
31      << Q.top()->Name;
32
33  Legolas.Health = 0; 
34
35  std::cout << "\nThe highest priority "
36               "character is still "
37            << Q.top()->Name;
38}
39

1The highest priority character is Legolas
2The highest priority character is still Legolas
3

The standard library does not have a class that implements a priority queue with reprioritization and dynamic priority. If we need that, we need to build it ourselves or look for 3rd party options outside of the standard library.