The Priority Queue (priority_queue) in C++

Lesson 8 of 11 · Data structures

A priority queue always gives the element with the highest (or lowest) priority, and adding and removing take only O(log n). It is used in Dijkstra's algorithm, for choosing "the next best one" and in many greedy algorithms.

Before you start: prerequisites – Queue, Stack.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Basic operations

OperationMeaningComplexity
pq.push(x)adds an elementO(log n)
pq.top()returns the element with the highest priority (does not remove it)O(1)
pq.pop()removes that elementO(log n)
pq.size(), pq.empty()the number of elements, whether it is emptyO(1)

Inside there is a heap – a tree in which every parent is larger than its children, so the largest element is always at the root. The header is <queue>.

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

int main() {
    priority_queue<int> maxHeap;                               // by default: the largest on top
    priority_queue<int, vector<int>, greater<int>> minHeap;    // the smallest on top
    for (int x : {5, 1, 8, 3}) {
        maxHeap.push(x);
        minHeap.push(x);
    }
    while (!maxHeap.empty()) { cout << maxHeap.top() << " "; maxHeap.pop(); }
    cout << "\n";
    while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); }
    cout << "\n";
    return 0;
}

Output:

8 5 3 1
1 3 5 8 

Pairs and a custom priority

If the queue holds pairs pair<int,int>, they are compared first by the first element, then by the second. A common trick: put the priority in the first element and the data (e.g. a graph node) in the second. A min-heap of pairs is written as priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> – that is exactly what the queue in Dijkstra's algorithm (SR) looks like.

For a more complex criterion you write a structure with a comparison operator; be careful, the logic is "reversed": the element for which the comparison returns true goes lower.

Typical uses

  • the k largest elements of a data stream – a min-heap of size k;
  • merging always the two smallest elements (ropes, Huffman coding);
  • job scheduling – always take the job with the highest priority or the earliest deadline;
  • shortest paths – Dijkstra, Prim (Prim's algorithm (SR)).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

The k largest numbers

n numbers (n ≤ 106) and a number k are read. Print the k largest, from the largest to smaller ones, using memory for only k numbers.

Example

Input

7 3
5 1 9 3 7 9 2

Output

9 9 7
TASK 02Difficulty: medium

Joining ropes

We have n pieces of rope of given lengths. Joining two pieces of lengths a and b costs a + b and gives a piece of length a + b. What is the lowest cost of joining all the pieces into one?

Example

Input

4
4 3 2 6

Output

29
TASK 03Difficulty: harder

Jobs with priorities

Jobs arrive over time: job i arrives at the moment t[i], lasts d[i] and has the priority p[i]. The processor runs one job at a time until it is finished; when it is free, it chooses among the jobs that have arrived the one with the highest priority (for the same priority – the one that arrived earlier). Print the order of execution (numbers from 1).

Example

Input

4
0 3 1
1 2 5
2 1 3
3 2 5

Output

1 2 4 3
Common mistakes and tips
  • The default priority_queue is a max-heap; for the smallest element on top add vector<T>, greater<T>.
  • top() on an empty queue is an error – always check empty() first.
  • The priority of an existing element in the queue cannot be changed; instead, insert a new pair and skip the outdated one when it comes out (that is how Dijkstra works).
  • If you need both the smallest and the largest element, or removing an arbitrary element, use multiset.

Check your knowledge

Open the quiz

Mini quiz: the priority queue

1. Which element does top() return for priority_queue<int>?




2. What is the complexity of the operation push?




3. Which queue is needed for Dijkstra's algorithm?