Priority Queue C++

How to Use Priority Queue in C++

In programming, queues are used to create data structures that store values in a first-in, first-out order.

When you’re coding in C++, you may want to create a queue that processes the element that has the highest priority. This would be instead of the element that comes before that item in the queue, which is the order used in regular queues.

That’s where the C++ priority queue comes in. This tutorial will discuss, with reference to examples, the basics of priority queues in C++, how to create a priority queue, and how to manipulate the data stored in a priority queue.

C++ Priority Queues

Queues are a type data structure which follow a first-in, first-out order. This means that the first item inserted into a queue is the first one that will be removed from the queue.

Let’s say you are waiting in line at a checkout in a supermarket. The first person who shows up to the line should be the first person served, because they have been waiting the longest. This is exactly how a queue works in programming.

However, there is another type of queue used in coding called a priority queue. Priority queues serve elements with the highest priority first, then serve elements with lower priorities. A real-world example of a priority queue would be a waitlist for a club which has a VIP list. If you’re a VIP, you should be admitted before everyone else who is waiting in line.

So, with a priority queue, you can skip the first-in, first-out structure, and instead process an element with the highest priority.

For instance, if you had a priority queue that contains the values 92, 1, and 102—which were inserted in that order—102 would be processed first, because it is the largest number and therefore has the highest priority. Here’s how the data would be stored in this priority queue:

As you can see, 102 is at the top of our queue, even though we added it in last. That’s because our elements in the priority queue are stored based on their size (or priority).

Create a Priority Queue

The C++ priority queue is contained within the C++ standard library. This means that, when we create a priority queue, we are referencing the standard library.

In addition, we need to import the queue class before we start working with a priority queue. Here’s the code we can use to import the queue class:

#include <queue>

Now that we’ve imported the queue class into our code, we can start creating priority queues. Here’s the syntax for creating a priority queue in C++:

priority_queue <dataType> queueName;

Let’s break down this syntax into its main components:

• priority_queue tells our program to create a priority queue.
• dataType is the type of data that will be stored in our priority queue.
• queueName is the name assigned to our queue.

Suppose we wanted to create a priority queue which stores the ticket numbers of people who are on a waitlist to enter an exclusive club.

Standard tickets, which give people no priority when entering the club, have a ticket number between 1 and 100. VIP tickets, which allow people to get in before standard ticket holders, have a ticket number between 100 and 200. The higher the customer’s ticket number, the earlier they should be able to enter the club.

Here’s the code we could use to create a priority queue to store these ticket numbers:

priority_queue <int> tickets;

In our example, we have declared a priority queue called tickets which stores integers. In this priority queue, the values with the highest number will be processed first in the queue. So, ticket holder #100 will be processed before ticket holder #99, for example.

Each element stored in a priority queue is called an item.

Add Item to Priority Queue

The priority queue push() method is used to add an item to a priority queue. push() accepts one parameter, which is the value you want to add to your queue.

Suppose we have just sold a new VIP ticket and we want to add them to our priority queue. Our ticket queue already contains the values for ticket holders 50, 75, and 149.

This VIP ticket has the ticket number 120, which means that they will be ahead of all standard ticket holders, but they will not be ahead of people who have a higher ticket number than them. We could use the following code to add them to a priority queue:

#include <iostream>
#include <queue>
using namespace std;
int main() {
	priority_queue <int> tickets;
	tickets.push(50);
	tickets.push(75);
	tickets.push(149);
	tickets.push(120);
	cout << tickets.top();
}

Our code returns:

149

Let’s break down our code. First, we have initialized a priority queue called tickets which stores integer values. Then we used push() to add 50, 75, and 149 to our queue, which are tickets that have already been sold.

We then used push() to add our new ticket, #120, to the tickets queue. Finally, we used top() to retrieve the item at the top of our queue (the item with the highest priority).

In a traditional queue — that uses the first-in, first-out structure — the top() method would return 50, which was the first item in the queue. However, because we have declared a priority queue, our program returns 149, which is the highest value in our queue. For reference, here is how the values in our queue are stored:

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

This table illustrates that the items in our queue are stored based on their value—the highest value is at the top of the queue—rather than the order in which they were inserted into our queue.

Retrieve Item from Priority Queue

When you’re working with a priority queue, you may want to retrieve the largest value in the queue. That’s where the top() method comes in.

Suppose you were about to admit someone into the club and you want to know which ticket holder is next in line. You could use the following code to find out the highest ticket number which exists in the queue:

#include <iostream>
#include <queue>
using namespace std;
int main() {
	priority_queue <int> tickets;
	tickets.push(50);
	tickets.push(75);
	tickets.push(149);
	tickets.push(120);
	cout << tickets.top();
}

This example is the same one we used to illustrate adding an item to a queue, and the example returns: 149. As you can see, top() retrieved the item at the top of our queue, which is the highest value in our queue.

Remove Item from Priority Queue

The priority queue pop() function is used to remove an item from a C++ priority queue.

pop() removes the largest item from a queue, and then places the second largest item at the beginning of the queue. pop() accepts no parameters, as it removes the largest item from the queue instead of a specific item.

Let’s return to our club example from earlier. Suppose that we are starting to let people into the club for the party. We want to remove the person with the highest priority from our queue, who has just been admitted, so that we are ready to admit new people into the club when a space opens up.

We could use the following code to remove the ticket number from our queue with the highest priority:

#include <iostream>
#include <queue>
int main() {
	priority_queue <int> tickets;
	tickets.push(50);
	tickets.push(75);
	tickets.push(149);
	tickets.push(120);
	tickets.pop();
	cout << tickets.top();
}

Our code returns:

120

In our example, we first declare a priority queue called tickets, which stores integer values. Then we add the values 50, 75, 149, and 120 to our queue.

We then use the pop() method to remove the item at the top of our priority queue, which is 149 in this case (remember, priority queues prioritize the highest value). Then, we print the item which is at the top of the queue using top() after pop() has been run.

So, in this case, 149 is removed. This means our program prints out 120 when the top() method is executed. 120 is the second-highest value in our queue and becomes the highest once 149 is removed.

Print a Priority Queue

The priority queue method does not include any functions that can be used to print the contents of a queue. However, we can use a standard for loop and the top(), empty(), and pop() methods to iterate through every item in a queue and print each one to the console.

Suppose we want to create a list of everyone who is on the waitlist to enter our club. We could do so using this code:

#include <iostream>
#include <queue>
int main() {
	priority_queue <int> tickets;
	tickets.push(50);
	tickets.push(75);
	tickets.push(149);
	tickets.push(120);
	priority_queue <int> new_queue = tickets;
	while (!new_queue.empty()) {
		cout << new_queue.top() << "\n";
		new_queue.pop();
	}
}

Our code returns:

149
120
75
50

Let’s break down our code. First, we declare a priority queue called tickets, and we use the push() method to add the values 50, 75, 149, and 20 to our priority queue.

Next, we declare a new priority queue called new_queue and assign it the same values that are stored in our tickets queue. We do this because we are going to remove items from this queue later in our code, and we don’t want to affect our initial queue.

On the next line, we initialize a while loop. The while loop evaluates the statement !new_queue.empty(), which means that it will run until the queue new_queue is empty.

In the body of our while loop, we use top() to retrieve the item at the top of our queue, then we print it to the console, followed by a new line character (represented by \n). We then use pop() to remove the item at the top of our queue.

This means that, next time the while loop runs, we can get the next-highest item and print it to the console, before we remove that item and repeat the process until the queue is empty.

Other Priority Queue Methods

The priority queue includes a few additional methods which can be used to interact with the data type. Here is a reference table that lists these methods:

Conclusion

The priority queue is used to create a queue which stores values based on their size. This means that the highest value is stored at the top of a priority queue, and subsequent items are stored in descending order.

This tutorial discussed, with reference to examples, the basics of priority queues, how to create a priority queue, and how to add, remove, and retrieve items from a priority queue. Now you have the information you need to start using priority queues in C++ like a pro!