What is Priority Queue in C++?

A priority queue is a container adapter in the Standard Template Library (STL) that stores elements based on priority.

By default, the largest element always has the highest priority and is always available at the top.

Unlike a regular queue, elements are not removed in the order they were inserted.

Think of a priority queue as the emergency room in a hospital. Patients are treated based on the seriousness of their condition rather than their arrival time.

Why does Priority Queue exist?

Many applications need to process data according to importance rather than insertion order. Instead of sorting the collection after every insertion, a priority queue automatically keeps the highest-priority element ready for removal.

• CPU scheduling
• Hospital emergency systems
• Network packet routing
• Job scheduling
• Graph algorithms
• Event simulation

Real-world use cases

• CPU process scheduling
• Hospital emergency rooms
• Dijkstra's shortest path algorithm
• Prim's Minimum Spanning Tree algorithm
• Event-driven simulations
• Airline reservation systems
• Task scheduling
• Online gaming matchmaking

Prerequisites

• Variables and data types
• Arrays
• Functions
• Loops
• Templates
• Basic STL containers
• std::queue (recommended)

Including the header

#include <queue>

Creating a priority queue

// Max Heap (default)
priority_queue<data_type> pq;

// Example:
priority_queue<int> numbers;
// The largest element always remains at the top.

// Min Heap
priority_queue<int, vector<int>, greater<int>> pq;

// Example:
priority_queue<int, vector<int>, greater<int>> numbers;
// The smallest element now has the highest priority.

Characteristics of Priority Queue

• Access method: highest priority first
• Default heap: max heap
• Min heap: supported
• Random access: not supported
• Iterators: not available
• Underlying container: std::vector

Common operations

• push() – insert an element
• pop() – remove the highest-priority element
• top() – access the highest-priority element
• size() – number of elements
• empty() – check whether the queue is empty

How a priority queue works

Suppose we insert 10, 30, 20, 50. Internally the elements form a heap with 50 at the top. Calling pop() removes 50, and the next highest-priority element, 30, automatically moves to the top.

Max heap vs min heap

• Max heap: largest element first, the default behavior, created with priority_queue<int>
• Min heap: smallest element first, uses the greater<T> comparator, created with priority_queue<int, vector<int>, greater<int>>

Example 1: Creating a max heap

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> numbers;

    numbers.push(30);
    numbers.push(10);
    numbers.push(50);
    numbers.push(20);

    cout << numbers.top();

    return 0;
}

// Output: 50

Example 2: Removing elements

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> values;

    values.push(5);
    values.push(25);
    values.push(15);

    values.pop();

    cout << values.top();

    return 0;
}

// Output: 15

Example 3: Min heap

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> numbers;

    numbers.push(40);
    numbers.push(10);
    numbers.push(30);
    numbers.push(20);

    cout << numbers.top();

    return 0;
}

// Output: 10

Example 4: Processing tasks by priority

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> tasks;

    tasks.push(3);
    tasks.push(5);
    tasks.push(1);
    tasks.push(4);

    while (!tasks.empty())
    {
        cout << "Processing Priority ";
        cout << tasks.top() << endl;

        tasks.pop();
    }

    return 0;
}

// Output:
// Processing Priority 5
// Processing Priority 4
// Processing Priority 3
// Processing Priority 1

Example 5: Hospital emergency system

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
    priority_queue<pair<int, string>> patients;

    patients.push({2, "Alice"});
    patients.push({5, "Bob"});
    patients.push({1, "Charlie"});

    while (!patients.empty())
    {
        cout << patients.top().second;
        cout << " (Priority ";
        cout << patients.top().first;
        cout << ")" << endl;

        patients.pop();
    }

    return 0;
}

// Output:
// Bob (Priority 5)
// Alice (Priority 2)
// Charlie (Priority 1)

Common mistakes and pitfalls

• Expecting FIFO behavior. Fix: a priority queue removes the highest-priority element first
• Assuming pop() returns the removed element. Fix: use top() before calling pop()
• Calling top() on an empty queue. Fix: check empty() first
• Using the default priority queue when a min heap is needed. Fix: use greater<T> as the comparator
• Trying to iterate through a priority queue. Fix: priority queues do not provide iterators

Best practices

• Always check empty() before calling top() or pop()
• Use a max heap when the largest value should be processed first
• Use a min heap with greater<T> when the smallest value has the highest priority
• Store custom objects using std::pair or define custom comparison functions for complex sorting
• Use std::priority_queue in graph algorithms such as Dijkstra's and Prim's algorithms for efficient performance

When not to use this

• FIFO behavior is required (use std::queue)
• LIFO behavior is required (use std::stack)
• Random access is needed (use std::vector)
• You need to search for arbitrary elements efficiently
• You need to iterate over elements in insertion order

Summary

• Priority Queue in C++ is a container adapter that processes elements according to priority
• By default, it behaves as a max heap, where the largest element is always at the top
• A min heap can be created using greater<T> as the comparison function
• Common operations include push(), pop(), top(), size(), and empty()
• Priority queues do not support random access or iterators
• They are widely used in scheduling systems, graph algorithms, and simulations where processing order depends on priority rather than insertion time

Frequently asked questions

What is the difference between a queue and a priority_queue?

A queue follows the FIFO (First In, First Out) principle, while a priority_queue removes the highest-priority element first, regardless of insertion order.

How do I create a min heap in C++?

Use the greater<T> comparator, as in priority_queue<int, vector<int>, greater<int>> pq. This makes the smallest element appear at the top.

Why doesn't pop() return the removed element?

Like other STL container adapters, pop() only removes the top element. Use top() to access the value before calling pop().

What is the time complexity of priority queue operations?

push() and pop() are O(log n), while top(), empty(), and size() are all O(1).

When should I use std::priority_queue instead of std::queue?

Use std::priority_queue when elements should be processed based on priority rather than the order they were inserted. Examples include CPU scheduling, shortest-path algorithms, and emergency response systems.