priority_queue: The Largest Leaves First, Whenever It Came

Maria runs the help desk of the school's computer lab, and every report there gets an urgency number. She always takes the most urgent open report next, whenever it came in. Module 6's queue would make the projector that died before an exam wait behind forty password resets. A vector would need a full scan, or a sort, before every take. This lesson gives her a container that hands back the largest first, and shows why that is cheap.

Who leaves first: the largest

Module 6's lesson 04 asked one question of every job: who leaves first? A stack answers the newest, and a queue the oldest. Maria needs the third answer, the most important, and its container is the priority_queue: it always gives back the largest value it holds. Here the same four urgencies arrive at both.

The queue gives the urgencies back as they came. The priority_queue gives back 9 first, although it arrived second. So with a priority_queue the order of arrival never decides; only the values do.

A heap: a tree with one promise

To find the largest quickly, push after push, a priority_queue keeps its values in a heap, a kind of tree. Each value sits in a node, and a node can have up to two children under it. The node right above a child is its parent, and the top node, with no parent, is the root.

A heap keeps one promise: every parent is at least as large as its children. So the values never shrink on the way up, and the root holds the largest of all. Nothing else is promised: two children can be in either order. So the largest always waits at the root, while the rest is only partly sorted.

The tree lives in a vector

The tree is not built from separate nodes. It is written into one vector, level by level and left to right. A level is one row of the tree, and a slot is one position in the vector, counted from 0. The drawing shows the heap that the next section builds.

Each level holds twice as many slots as the one above: 1, 2, 4, 8 and so on. So 7 values fill 3 levels, and 1,000,000 values need only 20. That number is about log₂ n, how many times you can halve n before you reach 1. Lesson 05 works out which slot is whose parent. So a value moves through at most about log₂ n levels, which keeps a heap fast.

A push climbs

Now watch the heap move. Six values go into an empty priority_queue<int>: 4, 9, 2, 7, 5 and 8. Step through them and watch where each new value lands, and how far it climbs.

Every push did the same two things. The new value went into the next free slot, on the bottom level. Then it climbed, swapping with its parent while it was larger; each such swap is called a sift up. 9 climbed to the root, 7 and 8 one level each, and 2 and 5 not at all. So a push makes at most one swap per level.

A pop sinks

A pop removes the root, and the heap must close the gap without breaking its promise. Watch two pops on the heap the six pushes built.

Each pop moved the last value into slot 0, since a vector removes its last slot cheaply. Then that value sank: while its larger child was larger, the two swapped, a step called a sift down. The larger child goes up, so the promise holds. So a pop, like a push, moves one value through at most about log₂ n levels.

After each whole push or pop, the widgets show the vector GCC 12's priority_queue held on Compiler Explorer. Inside a pop the library takes a shortcut to the same vector, which lesson 05 shows. So these pictures are the real layout.

The syntax you need on day one

#include <queue>

priority_queue<T> pq;      an empty priority_queue of T
pq.push(x);                add x; it climbs to its place
pq.top()                   the largest element; it stays in
pq.pop();                  remove the largest; returns nothing
pq.size()    pq.empty()    how many, and whether there are none

#include <functional>     for greater
#include <vector>
priority_queue<T, vector<T>, greater<T>> small;
                           the smallest on top instead

So a priority_queue has the three working calls of a stack, push, top and pop, and top() always shows the largest.

push, top and pop

push(x) puts x into the heap. top() tells you the largest value inside now, and pop() removes it. This program prints the top and the size after each change.

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

int main() {
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(2);
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    pq.pop();
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    pq.push(7);
    cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    return 0;
}

top 9, size 3
top 4, size 2
top 7, size 3

After the pop, 4 became the top, because it was the largest of what was left. Then 7 arrived and went straight to the top, ahead of the older 4. So top() always answers with the largest value still inside, whenever it came.

pop returns nothing: read first, then pop

Bob wants the largest value and its removal in one line, so he writes this.

priority_queue<int> pq;
pq.push(4);
int x = pq.pop();

GCC 12 stops at the runner's flags with error: void value not ignored as it ought to be. void means "no value": pop() removes the top and hands nothing back, just like a stack's pop() in Module 6. The fix is two lines, a read and then a pop.

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

int main() {
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(2);
    int x = pq.top();
    pq.pop();
    cout << "took " << x << ", now the top is " << pq.top() << '\n';
    return 0;
}

took 9, now the top is 4

So the pair you met in Module 6 stays: look with top(), then pop().

The smallest first, in one line

Some jobs want the smallest first: the cheapest fare, the shortest wait. Give the priority_queue two more things in its angle brackets: the vector it keeps inside, and greater<int>, which turns the order around. Lesson 02 explains both; for now, copy the line.

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

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : {4, 9, 2, 7, 5, 8}) {
        pq.push(x);
    }
    cout << "smallest first:";
    while (!pq.empty()) {
        cout << ' ' << pq.top();
        pq.pop();
    }
    cout << '\n';
    return 0;
}

smallest first: 2 4 5 7 8 9

The loop while (!pq.empty()) reads the top, prints it and pops it until nothing is left, which is called a drain. So one longer declaration turns the largest-first heap into a smallest-first one, and every call stays the same.

The empty priority_queue: Zara's first test

Zara always tries the empty case first. She asks an empty priority_queue for its top.

priority_queue<int> pq;
cout << "top: " << pq.top() << '\n';

It compiled with no message at the runner's flags. On Compiler Explorer's GCC 12.2, one run printed nothing and crashed with SIGSEGV, the signal for reading memory it does not own. Even top: never appeared, because cout still held it. Then she pops an empty one.

priority_queue<int> pq;
pq.pop();
cout << "size after pop: " << pq.size() << '\n';

That run printed size after pop: 18446744073709551615 and ended normally. The pop slid the vector's end below its start, so the size wrapped around to the largest number it can hold. A push(7) and a top() after it crashed with SIGSEGV. Both are undefined behaviour: the C++ standard says nothing about what happens. So write if (!pq.empty()) before every top() or pop() whose input you do not control.

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

int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while (!pq.empty()) {
        cout << "pop " << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

pop 8
pop 5
pop 1

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

int main() {
    priority_queue<int> scores;
    for (int s : {120, 340, 90, 410, 275}) {
        scores.push(s);
        cout << "pushed " << s << ", best so far " << scores.top() << '\n';
    }
    scores.pop();
    cout << "the best player leaves; next best " << scores.top() << '\n';
    return 0;
}

pushed 120, best so far 120
pushed 340, best so far 340
pushed 90, best so far 340
pushed 410, best so far 410
pushed 275, best so far 410
the best player leaves; next best 340

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

int main() {
    priority_queue<string> words;
    words.push("pear");
    words.push("apple");
    words.push("fig");
    words.push("banana");
    cout << "largest first:";
    while (!words.empty()) {
        cout << ' ' << words.top();
        words.pop();
    }
    cout << '\n';
    return 0;
}

largest first: pear fig banana apple

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

int main() {
    int n;
    cin >> n;
    priority_queue<int> marks;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        marks.push(m);
    }
    int place = 1;
    while (!marks.empty()) {
        cout << place << ". " << marks.top() << '\n';
        marks.pop();
        place++;
    }
    return 0;
}

1. 92
2. 92
3. 88
4. 81
5. 75
6. 67
7. 59

#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(5);
    cout << pq.top() << '\n';
    return 0;
}

priority_queue<int> pq;
pq.push(5);
cout << pq.front() << '\n';

priority_queue<int> fares;
fares.push(30);
fares.push(12);
fares.push(45);
cout << "cheapest fare first:";
while (!fares.empty()) {
    cout << ' ' << fares.top();
    fares.pop();
}
cout << '\n';

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    priority_queue<int> reports;
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "add") {
            int urgency = 0;
            cin >> urgency;
            // Add the new report's urgency to reports.
        } else {
            // op is "take": print the highest urgency and remove it,
            // or print none if no report is open.
        }
    }

    // Print the urgencies still open, from the highest to the lowest,
    // separated by single spaces, or the word empty if none is left.

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<int> tallest;
    priority_queue<int, vector<int>, greater<int>> shortest;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        // Push h into both heaps.
    }

    // Print n heights on one line, separated by single spaces: the tallest,
    // then the shortest, then the next tallest, and so on. Every student
    // stands in the row exactly once, so print exactly n heights.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> heap;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        heap.push_back(x);
        // x is now in the last slot. While it is larger than the value in
        // its parent's slot, swap the two and move up to the parent's slot.
        // Then print heap, slot 0 first, separated by single spaces.
    }
    return 0;
}

Next, lesson 02 goes through every operation of priority_queue, one by one, each with its cost, and every way to choose its order.