Priority queue

A priority queue keeps a set of numbers that changes over time and gives you the smallest (or the largest) of them at any moment, whatever order they came in.

Use it when new numbers keep arriving between pops. If all the numbers are known from the start, a sorted array does the job faster. If the oldest number must come out first, use a queue.

Operation	What it does	Time
`push(x)`	adds `x`	$O (lo g n)$ O(\log n)
`top()`	the smallest number	$O (1)$
`pop()`	removes the smallest number	$O (lo g n)$ O(\log n)
`empty()`, `size()`	is it empty, how many numbers	$O (1)$

Let's run a few operations on a priority queue to see how it works.

A priority queue on a few operations, the numbers in the order they came, step 1.

The priority queue is empty.

1/14

Fig. 1. The numbers in the order they came. pop takes the smallest, wherever it is.

How it works

A priority queue is usually a binary heap. It keeps the numbers in a binary tree, a graph with one vertex on top where every vertex has at most two children right below it. The tree is filled level by level, each level from left to right, without gaps. Every number is no larger than its children, so going up the numbers never grow and the number on top is the smallest.

A binary heap drawn as a tree with 1 on top, 2 and 5 below it, and 8 and 6 below 2, each vertex marked with its place 1 to 5; beside it the same heap as the array 1 2 5 8 6, each level in the same colour in the tree and in the array.

Fig. 2. The heap after push 5, 8, 2, 6 and 1, as a tree and as the array that stores it. Each level has its own colour, and the array holds the levels one after another, top level first. The small grey number by each vertex is its place: its index in the array.

The places are numbered level by level: the top is place 1, the next level holds places 2 and 3, the next places 4 to 7. So the tree needs nothing but an array with places 1 to $n$ . Right below place $i$ are places $2 i$ and $2 i + 1$ 2i + 1, and right above it is place $i /2$ , rounded down. In Fig. 2, right below place 2 are places 4 and 5, which hold 8 and 6.

push and pop each restore the rule by swaps along one path between the top and the bottom:

push: put the new number in the next free place, at the end of the array. Then let it rise: while it is smaller than the number right above it, swap the two.
pop: take the number on top. Move the last number of the array to the top. Then let it sink: while the smaller of the numbers right below it is smaller than it, swap it with that number.

A binary heap as a tree and as an array, on the operations of Fig. 1, step 1.

The heap is empty.

1/23

Fig. 3. The heap on the operations of Fig. 1. The blue number is moving, the red number is taken.

After these operations the heap is 4 6 5 8 7, and the operations printed 1, 2, 4 and 5: the same as in Fig. 1, with no search through the numbers.

Each level has twice as many places as the one above, so a heap of $n$ numbers has about $lo g_{2} n$ \log_2 n levels. push and pop make at most one swap per level, so they take $O (lo g n)$ O(\log n) time, and the heap uses $O (n)$ memory.

In C++

The C++ priority queue is in the header <queue>. The line priority_queue<int> pq; declares an empty priority queue that gives the largest number. For the smallest, copy this line:

priority_queue<int, vector<int>, greater<int>> pq;

vector<int> is where the numbers are kept, and greater<int> turns the order round.

This program runs commands on a priority queue that gives the smallest. The input is q ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5), then q lines, each push x ( $∣ x ∣ \leq 1 0^{9}$ |x| \le 10^9), pop, top or size; pop and top never come on an empty priority queue. pop and top print the smallest number, size the count. The example above is this input:

11
push 5
push 8
push 2
push 6
push 1
pop
push 4
pop
push 7
top
size

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

int main() {
    int q;
    cin >> q;
    priority_queue<int, vector<int>, greater<int>> pq;   // gives the smallest

    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            pq.push(x);
        } else if (cmd == "pop") {
            cout << pq.top() << '\n';   // read the top first
            pq.pop();                   // pop returns nothing
        } else if (cmd == "top") {
            cout << pq.top() << '\n';
        } else if (cmd == "size") {
            cout << pq.size() << '\n';
        }
    }
}

Examples of use

Dijkstra's algorithm

Dijkstra's algorithm finds shortest paths in a graph. Found vertices wait in a priority queue as pairs (distance, vertex), and the closest one is taken next. A shorter distance is pushed as a new pair, and the old pair is skipped later.

Combining the two smallest

Adding two numbers costs their sum, and the sum takes their place; all the numbers must be added into one at the least total cost (practice problem 1228). Always add the two smallest: pop two, push their sum, repeat until one number is left. The new sum is not always the smallest. For 1, 1, 1 and 1 the priority queue pays 2 + 2 + 4 = 8, while adding in sorted order pays 2 + 3 + 4 = 9.

The counter that becomes free first

$k$ counters serve one line of people, each person needing a known time, and the next person goes to the counter that becomes free first (practice problem 3004). Keep the times when the counters become free in a priority queue, all 0 at the start. For each person, pop the earliest time $t$ and push $t$ plus the person's time.

Common mistakes

Sinking into the first place below instead of the smaller one, which can put a larger number above a smaller one. Swap with the smaller of the two numbers below.
Reading the heap's array as sorted. Only the top is known, and the last place need not hold the largest number.
Adding up sums in int when combining the two smallest, though the last sum can reach $1 0^{10}$ 10^{10}. Use long long for the priority queue and the total.

Similar structures

A queue gives the oldest number first and a stack the newest, whatever their values.

A set or multiset keeps the numbers sorted, gives both the smallest and the largest, and can remove any number. A set drops repeated numbers; a multiset keeps them.