Code has been added to clipboard!

Usage and Methods of Priority Queue in C++

Reading time 3 min
Published Aug 30, 2019
Updated Sep 27, 2019

TL;DR – C++ priority queue processes the element with the highest priority, instead of the ones that come before it.

What is a Priority Queue?

As the name implies, a C++ priority queue is a queue that processes the element that has the highest priority, instead of the one that comes before it.

The function compares elements to see if any of them have a priority set and moves the queue appropriately.

How C++ Priority Queue Works

The priority queue allows you to skip the line and process an element you prioritize first – ignoring the first in, first out logic.

You can make use of the standard library to apply a priority queue in C++ with the command std::priority_queue along with an interface like push(), pop() , and top(). To understand how each of them works, see the sections below.

Adding Elements

You can add an element to the queue by using the push() interface.

Example
// CPP program
// Adding push() function
#include <iostream>

#include <queue>

using namespace std;

int main() {
    // new empty queue
    priority_queue < int > pqueue;
    pqueue.push(3);
    pqueue.push(5);
    pqueue.push(1);
    pqueue.push(2);
    // queue is now 5, 3, 2, 1

    // printing queue
    while (!pqueue.empty()) {
        cout << ' ' << pqueue.top();
        pqueue.pop();
    }
}

The output will be 5 3 2 1.

Accessing the Largest Elements

You can also reference the largest element of the queue by using top():

Example
// CPP program
// Adding top() function
#include <iostream>

#include <queue>

using namespace std;

int main() {
    priority_queue < int > pqueue;
    pqueue.push(5);
    pqueue.push(1);
    pqueue.push(7);

    // Priority queue top
    cout << pqueue.top();
    return 0;
}

The code above will result in displaying the largest element, which is 7.

Removing the Largest Elements

The process will remove the largest element on the queue and place the second largest at the beginning, taking the position of the former largest element. You can use the interface pop to do so.

Example
// CPP program
// Adding pop() function
#include <iostream>

#include <queue>

using namespace std;

int main() {
    // empty queue
    priority_queue < int > pqueue;
    pqueue.push(0);
    pqueue.push(1);
    pqueue.push(2);
    // queue becomes 2, 1, 0

    pqueue.pop();
    pqueue.pop();
    // queue becomes 0

    // printing queue
    while (!pqueue.empty()) {
        cout << ' ' << pqueue.top();
        pqueue.pop();
    }
}

In the code above, there’s a queue containing 2, 1, and 0. Since pqueue.pop() is written twice, it erases two of the highest elements (2 and 1), leaving only 0.

Methods of Priority Queues

  • priority_queue::empty() – the empty() function is to check whether the element is empty or not.
  • priority_queue::size() – the size() function detects and returns the number of elements contained in the queue.
  • priority_queue::top() – the top() accesses the largest element of the stack.
  • priority_queue::push() – the push() function inserts a new element to the queue.
  • priority_queue::pop() – the pop() function erases the first element from the queue.
  • priority_queue::swap() – the swap() to swap the content between two priority queues of the same size and type.
  • priority_queue::emplace() – the emplace() is used to add a new element and put it to the top of the queue.
  • priority_queue value_type represents the first template parameter.

Priority Queue C++: Useful Tips

  • Since a priority queue is an abstract data type, it can also be implemented with the heap method.
  • Elements that have the same priority follow the FIFO (First In, First Out) basis. Keep this in mind in case the result of your priority queue still follows the FIFO basis.
  • There are three operations that are supported by priority queues: is_empty to check if there is no element in the queue, insert_with_priority to insert an element to the queue with a certain priority, andPull_highest_priority_element to pull the element that has the highest priority in the queue and display it.
Switch
Array
String
String to Int
Getline
Vectors
Linked List
Priority Queue
For Loop
Map
Random Number Generator
GDB Debugger
Smart pointers