C++ Priority Queues

Master priority queues with a complete guide, starting from the basics, using the standard library’s std::priority_queue.
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

145.jpg
Ryan McCombe
Ryan McCombe
Posted

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:

#include <queue>

int main() {
  std::priority_queue<int> Numbers;
}

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:

#include <queue>
#include <vector>

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{
      Source.begin(), Source.end()};
}

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

#include <queue>

int main() {
  std::priority_queue<int> Numbers;
  std::priority_queue<int> Copy{Numbers};
}

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):

#include <queue>

int main() {
  std::priority_queue<int> Numbers;
  std::priority_queue Copy{Numbers};
}

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:

#include <queue>
#include <vector>

int main() {
  std::priority_queue<int, std::vector<int>>
      Numbers;

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.

#include <deque>
#include <queue>

int main() {
  std::priority_queue<int, std::deque<int>>
      Numbers;
}

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:

#include <queue>
#include <vector>

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{{}, Source};
}

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:

#include <queue>
#include <vector>

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{
      {}, std::move(Source)};
}

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

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:

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

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{
      {}, std::move(Source)};

  std::cout << "The top of the queue is "
            << Numbers.top();
}
The top of the queue is 3

pop()

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

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

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{
      {}, std::move(Source)};

  std::cout << "The top of the queue is "
            << Numbers.top();

  Numbers.pop();

  std::cout << "\nThe top of the queue is now "
            << Numbers.top();
}
The top of the queue is 3
The top of the queue is now 2

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:

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

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:

using queue = std::priority_queue<
    int,
    std::vector<int>,
    decltype(Comparer)>;

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

using queue = std::priority_queue<
    int,
    std::vector<int>,
    std::function<bool(int, int)>>;

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

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:

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

using queue = std::priority_queue<
    int,
    std::vector<int>,
    std::function<bool(int, int)>>;

queue Numbers{Comparer};

Here is a complete working example:

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

int main() {
  std::vector<int> Source{1, 2, 3};

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

  using queue = std::priority_queue<
      int, std::vector<int>,
      std::function<bool(int, int)>>;

  queue Numbers{Comparer, std::move(Source)};

  std::cout << "The top of the queue is "
            << Numbers.top();

  Numbers.pop();

  std::cout << "\nThe top of the queue is now "
            << Numbers.top();
}
The top of the queue is 1
The top of the queue is now 2

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:

#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int> Nums;
  Nums.emplace(10);

  std::cout << Nums.top()
            << " is at the top of the queue";
}
10 is at the top of the queue

push()

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

#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int> Nums;

  int x{10};
  int y{20};

  // Copy
  Nums.push(x); 

  // Move
  Nums.push(std::move(y));

  std::cout << "We have " << Nums.size()
            << " items in the queue";
}
We have 2 items in the queue

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:

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

int main() {
  std::priority_queue<int> Nums;
  std::vector Range{1, 2, 3};

  Nums.push_range(Range);

  std::cout << "We have " << Nums.size()
            << " items in the queue";
}
We have 3 items in the queue

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:

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

int main() {
  std::vector<int> Source{1, 2, 3};
  std::priority_queue<int> Numbers{
      {}, std::move(Source)};

  std::cout << "The queue's size is "
            << Numbers.size(); 

  Numbers.pop();

  std::cout << "\nThe size is now "
            << Numbers.size(); 
}
The queue's size is 3
The size is now 2

empty()

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

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

int main() {
  std::priority_queue<int> Numbers;
  Numbers.emplace(5);

  std::cout << "The queue "
            << (Numbers.empty() ? "is" 
                                : "is not")
            << " empty\n";

  Numbers.pop();

  std::cout << "Now the queue "
            << (Numbers.empty() ? "is" 
                                : "is not")
            << " empty";
}
The queue is not empty
Now the queue is empty

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:

#include <iostream>
#include <queue>

class Character {
 public:
  Character(std::string Name, int Level)
      : Name{Name}, Level{Level} {}
  std::string Name;
  int Level;
};

int main() {
  auto compare{[](Character& x, Character& y) {
    return x.Level < y.Level;
  }};

  using QueueType = std::priority_queue<
      Character, std::vector<Character>,
      decltype(compare)>;

  QueueType Q{compare};

  Q.emplace("Aragorn", 40);
  Q.emplace("Gandalf", 50);
  Q.emplace("Bilbo", 20);
  Q.emplace("Frodo", 30);

  int SpaceInParty{3};

  while (SpaceInParty && !Q.empty()) {
    std::cout << "Adding " << Q.top().Name
              << " (" << Q.top().Level
              << ") to the party\n";
    Q.pop();
    --SpaceInParty;
  }

  std::cout << Q.size()
            << " Character is still in queue";
}
Adding Gandalf (50) to the party
Adding Aragorn (40) to the party
Adding Frodo (30) to the party
1 Character is still in queue

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:

#include <iostream>
#include <queue>

class Character {
 public:
  Character(std::string Name, int Health)
      : Name{Name}, Health{Health} {}
  std::string Name;
  int Health;
};

int main() {
  auto compare{[](Character* x, Character* y) {
    return x->Health < y->Health;
  }};

  using QueueType = std::priority_queue<
      Character*, std::vector<Character*>,
      decltype(compare)>;

  QueueType Q{compare};

  Character Legolas{"Legolas", 100};
  Character Gandalf{"Gandalf", 50};

  Q.push(&Legolas);
  Q.push(&Gandalf);

  std::cout
      << "The highest priority character is "
      << Q.top()->Name;

  Legolas.Health = 0; 

  std::cout << "\nThe highest priority "
               "character is still "
            << Q.top()->Name;
}
The highest priority character is Legolas
The highest priority character is still Legolas

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.

Was this lesson useful?

Edit History

  • — Created

Ryan McCombe
Ryan McCombe
Posted
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

7a.jpg
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access!

This course includes:

  • 106 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

Stack Data Structures using std::stack

An introduction to the stack data structure, and the C++ standard library implementation - std::stack
3D concept art of an office worker
Contact|Privacy Policy|Terms of Use
Copyright © 2023 - All Rights Reserved