C++ Lesson 46 – Priority Queue | Dataplexa

STL · Lesson 46

Priority Queue

A queue serves the oldest first. A priority queue serves the most important first. Hospitals, operating systems and path-finding programs all use it: the most urgent patient, the most urgent job, the closest city — they all jump the line. In C++, that is std::priority_queue, a heap in disguise.

1. What Is a Priority Queue?

A priority queue is an STL container where every value carries a priority, and the value with the highest priority always sits on top. By default, the biggest value has the highest priority — so the largest number comes out first, no matter when it arrived.

Think of a hospital emergency room. A patient with a broken finger waits; a patient with chest pain goes first. It does not matter who arrived earlier — it matters who is most urgent. A priority queue works the same way: importance, not arrival time, decides who is next.

To use one, include the <queue> header and write std::priority_queue<Type>. Like a stack and a queue, it is a container adaptor — this time sitting on a vector — and it hides everything except six simple operations: push, top, pop, empty and size. There are no iterators and no random access, and the values below the top are not sorted — only the top is guaranteed to be the biggest.

2. Your First Priority Queue

Let us push four numbers into a priority queue and watch what comes out first. The numbers went in as 5, 1, 9, 3 — but the queue serves them by size, not by arrival.

Code story: We create a priority_queue of integers and push 5, then 1, then 9, then 3. top() gives us 9 — the biggest number, even though it arrived third. We pop once — 9 leaves — and now 5 is on top. The size tells us 3 values are left.

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

int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(9);
    pq.push(3);

    cout << "Top: " << pq.top() << endl;
    pq.pop();
    cout << "After pop, top: " << pq.top() << endl;
    cout << "Size: " << pq.size() << endl;
    return 0;
}
Top: 9
After pop, top: 5
Size: 3

What just happened? push(9) put the biggest value on top, so top() returned 9. pop() removed it, and 5 — the next biggest — rose to the top. size() counted the three values still waiting. Arrival order never mattered.

3. push, top, and pop

The same three functions do the work, with one difference: push() inserts a value in its priority place, not at the end. push(value) adds a value; top() returns the highest-priority value without removing it; pop() removes the top value and returns nothing — so read the value with top() first, and only then pop it.

The classic pattern is a serving loop: while the queue is not empty, read the top, serve it, then pop it. It empties the queue in priority order — biggest first.

Code story: We push 4, 7, 2 and 9 into a priority queue, then empty it with a while loop. Each round prints the current top and pops it. They come out as 9, 7, 4, 2 — biggest first, smallest last. At the end empty() returns 1, meaning true.

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

int main() {
    priority_queue<int> pq;
    pq.push(4);
    pq.push(7);
    pq.push(2);
    pq.push(9);

    while (!pq.empty()) {
        cout << "Serving: " << pq.top() << endl;
        pq.pop();
    }
    cout << "Empty: " << pq.empty() << endl;
    return 0;
}
Serving: 9
Serving: 7
Serving: 4
Serving: 2
Empty: 1

What just happened? The loop ran four times. First top() was 9, then 7, then 4, then 2 — the values in decreasing order, even though they were pushed in the order 4, 7, 2, 9. Once the queue was empty the loop stopped, and empty() returned 1.

4. Smallest First: the greater Comparator

By default a priority queue is a max-heap: the biggest value sits on top. But sometimes you want the smallest first — the shortest distance, the cheapest price, the nearest city. For that, you pass a comparator: priority_queue<int, vector<int>, greater<int>> turns it into a min-heap, with the smallest value on top.

The three template arguments are: the value type, the backing container (a vector), and the comparator (less for biggest-first — the default — or greater for smallest-first). You will use the min-heap version constantly in graph algorithms.

Code story: We build a min-heap with the greater comparator and push 5, 1, 9 and 3. Now top() gives us 1 — the smallest. We pop and print the new top each time: 3, then 5, then 9. The same four numbers come out in the opposite order from the max-heap, just because we changed one template argument.

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

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(5);
    pq.push(1);
    pq.push(9);
    pq.push(3);

    cout << "Smallest first: " << pq.top() << endl;
    pq.pop();
    cout << "Then: " << pq.top() << endl;
    pq.pop();
    cout << "Then: " << pq.top() << endl;
    pq.pop();
    cout << "Then: " << pq.top() << endl;
    return 0;
}
Smallest first: 1
Then: 3
Then: 5
Then: 9

What just happened? With greater as the comparator, the heap put the smallest value on top. Each pop revealed the next smallest: 1, 3, 5, 9 — the numbers in increasing order. Same container, same four numbers — the comparator flipped the order.

5. Storing Pairs and Tasks

A priority alone is rarely enough — you usually want the value attached to it. That is what pairs are for: push a pair<priority, task>, and the queue orders the pairs by their first element, the priority number. The biggest priority wins, and the task rides along with it.

Pairs compare first by their first element, then by their second — so two tasks with the same priority would be ordered by their name. For most jobs, the priority number is all you need.

Code story: Three tasks go into a priority queue as pairs of a priority number and a task name: Email (3), Call mom (1) and Pay bills (5). top() gives us the pair with the biggest priority — Pay bills, 5. We pop it, and the new top is Email with priority 3. The number decides; the name rides along.

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

int main() {
    priority_queue<pair<int, string>> tasks;
    tasks.push({3, "Email"});
    tasks.push({1, "Call mom"});
    tasks.push({5, "Pay bills"});

    cout << "Top priority task: " << tasks.top().second
         << " (" << tasks.top().first << ")" << endl;
    tasks.pop();
    cout << "Next: " << tasks.top().second
         << " (" << tasks.top().first << ")" << endl;
    return 0;
}
Top priority task: Pay bills (5)
Next: Email (3)

What just happened? The queue compared the pairs by their first element — the priority number. Pay bills had the biggest priority, 5, so it sat on top. After popping it, Email (3) took the top. The .first was the priority and the .second was the task name.

6. Priority Queue Operations at a Glance

That is the whole toolbox — a handful of operations cover everything a priority queue does. Here they are in one place:

OperationWhat it doesExampleResult
pq.push(5)Adds 5 and puts it in its priority placepq.push(5)Top may change
pq.top()Returns the highest-priority value, without removing itpq.top()9
pq.pop()Removes the top value; returns nothingpq.pop()Top is gone
pq.empty()Tells you whether the queue holds nothingpq.empty()1 or 0
pq.size()Counts how many values are storedpq.size()Number of values

Before you call top() or pop(), always ask whether the queue has anything in it — empty() returns 1 when it holds nothing. And remember the two flavours: a max-heap puts the biggest on top (the default), a min-heap puts the smallest on top. The same values behave differently only because of the comparator:

Code story: We build two heaps holding the same numbers, 4 and 8. One is a plain priority_queue — a max-heap — and its top is 8. The other is built with greater — a min-heap — and its top is 4. Same numbers, same container, two different answers: the comparator decides.

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

int main() {
    priority_queue<int> maxHeap;   // largest on top (default)
    maxHeap.push(4);
    maxHeap.push(8);
    cout << "Max-heap top: " << maxHeap.top() << endl;

    priority_queue<int, vector<int>, greater<int>> minHeap;  // smallest on top
    minHeap.push(4);
    minHeap.push(8);
    cout << "Min-heap top: " << minHeap.top() << endl;
    return 0;
}
Max-heap top: 8
Min-heap top: 4

What just happened? Both heaps stored 4 and 8. The max-heap reported 8 as its top, the min-heap reported 4 — the same two numbers, two different winners. The third template argument, the comparator, is the only thing that changed.

7. A Real Example: Hospital Triage

Here is the priority queue doing the job it was made for. Four patients arrive at an emergency room with different severity scores — the higher the score, the more urgent the case. A plain queue would treat them in arrival order; a priority queue treats the most urgent first.

Code story: Each patient is a pair of a severity score and a name: Ravi (2), Maya (5), Arjun (1) and Neha (4). They join the queue in arrival order, but a while loop treats them by severity: each round prints the name and severity of the patient on top, then pops them. Maya, the most urgent, goes first; Arjun, the least urgent, goes last.

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

int main() {
    priority_queue<pair<int, string>> er;  // severity, name
    er.push({2, "Ravi"});
    er.push({5, "Maya"});
    er.push({1, "Arjun"});
    er.push({4, "Neha"});

    while (!er.empty()) {
        cout << "Treating " << er.top().second
             << " (severity " << er.top().first << ")" << endl;
        er.pop();
    }
    return 0;
}
Treating Maya (severity 5)
Treating Neha (severity 4)
Treating Ravi (severity 2)
Treating Arjun (severity 1)

What just happened? The patients arrived as Ravi, Maya, Arjun, Neha — but the queue served them by severity: 5, 4, 2, 1. Maya waited the least because she was the most urgent. That is exactly what a real triage system does.

8. Dijkstra: The Priority Queue's Famous Job

The priority queue's most famous job in computer science is Dijkstra's shortest-path algorithm. It finds the cheapest way from one place to everywhere else on a map. At every step it picks the closest unvisited city — and a min-heap priority queue is exactly the tool that always hands you the closest one.

Code story: Our map has 4 cities. From city 0, the road to city 1 costs 4 and the road to city 2 costs 1; from city 2, the road to city 1 costs 2 and to city 3 costs 5; from city 1, the road to city 3 costs 1. Dijkstra starts at city 0 with distance 0 and keeps the nearest unexplored city on top of a min-heap. Watch the answer: city 2 is reached for 1, city 1 for 3 (a cheaper way through city 2), and city 3 for 4.

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

int main() {
    // Edges: 0-1 (4), 0-2 (1), 2-1 (2), 1-3 (1), 2-3 (5)
    vector<vector<pair<int, int>>> graph = {
        {{1, 4}, {2, 1}},   // from 0: to 1 cost 4, to 2 cost 1
        {{3, 1}},            // from 1: to 3 cost 1
        {{1, 2}, {3, 5}},   // from 2: to 1 cost 2, to 3 cost 5
        {}                   // from 3: none
    };
    const int INF = 1000000;
    vector<int> dist(4, INF);
    dist[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d != dist[u]) continue;
        for (auto edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    cout << "Shortest distances from 0: ";
    for (int d : dist) cout << d << " ";
    cout << endl;
    return 0;
}
Shortest distances from 0: 0 3 1 4

What just happened? City 2 is the cheapest first step (cost 1), and through city 2 the road to city 1 costs only 3 — cheaper than the direct road of 4. Then city 3 is reached through city 1 for 4. The min-heap always handed us the closest city next, and each city's shortest distance was found exactly once.

Three containers, three different promises about order. Choose by what must come out first:

ContainerOrderAddRemoveBest for
std::priority_queueHighest priority firstpush()pop() from topScheduling, Dijkstra, top-k
std::queueFirst in, first outpush() at the backpop() from the frontLines, BFS, printing
std::setSorted, uniqueinsert()erase()Ordered unique values

9. Common Mistakes

Watch out for these five traps — every beginner meets at least one of them:

MistakeWhat happensFix
Expecting FIFO order from a priority queueThe biggest value comes out first, not the oldestUse a queue if you need first-in, first-out
Calling top() or pop() on an empty priority queueUndefined behaviour — the program can crash or print garbageCheck empty() first
Using pop() to get the valuepop() returns nothing, so the value is lostCall top() first, save the value, then pop()
Forgetting greater when you want the smallest firstThe default is a max-heap, so the largest value sits on topWrite priority_queue<int, vector<int>, greater<int>>
Forgetting #include <queue>The compiler says "priority_queue was not declared in this scope"Add #include <queue> at the top of the file

Practice — try it yourself

1. Push the numbers 3, 9, 1, 7, 5 into a priority_queue and print them in the order they come out.

2. Build a min-heap and print the numbers 10, 4, 8, 2 in order from smallest to largest.

3. Write a hospital triage program: patients with severity scores — print them in the order they should be treated.

4. Use a priority_queue to find the 3 largest numbers in a list of 20 numbers.

What is a std::priority_queue?


By default, which value sits on top of a priority_queue<int>?


Which algorithm relies on a priority queue?


Fill in the blanks — type the missing word into the box.

A priority_queue serves the value first by default.


To make a min-heap, use the comparator .


Use pq.() to read the top value without removing it.


UP NEXT

Lesson 47 — STL Algorithms

Next, meet the STL algorithms — sort, find, count and more, ready-made functions that work on any container. One line of code replaces whole loops.

Go to Lesson 47 →