Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::priority_queue class

Reference for std::priority_queue: a max-heap adapter with push, top and pop, min-heaps with std::greater, custom comparators and Dijkstra-style use.

std::priority_queue<T> is a container adapter that always gives you the largest element first. You push elements in any order, top() returns the greatest one, and pop() removes it. Internally it keeps a binary heap inside a std::vector using std::make_heap, std::push_heap and std::pop_heap, which is why it is also called a heap.

Pushing and popping take O(log n); reading top() is O(1). Only the top is visible: you cannot iterate over the queue, search it, or change the priority of an element already inside. To get the smallest element first, give it the comparator std::greater<T>. It is the standard tool for schedulers, "top k" problems, merging sorted streams and Dijkstra's algorithm.

C++
#include <queue>
std::priority_queue<int> pq;
pq.push(3);  pq.push(9);  pq.push(5);
pq.top();    // 9

Try it

C++ Max-heap and min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Custom ordering: task scheduler and pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class priority_queue;

void push(const T& v);    void push(T&& v);
template <class... A> void emplace(A&&... args);
void pop();
const T& top() const;
bool empty() const;       size_type size() const;
Name Description
Container Underlying random-access sequence, vector by default (deque also works).
Compare Ordering where comp(a, b) being true means a has lower priority than b. The top is the element no other element is greater than.
v Value to add.

Returns: top() returns a const reference to the highest-priority element; pop() returns nothing.

Errors / undefined behavior: top() or pop() on an empty queue is undefined. A comparator that is not a strict weak ordering gives undefined behavior.

Usage notes

  • Default is a max-heap. The comparator std::less puts the largest on top. This feels backwards at first: with a custom comparator, "less" means "comes out later".
  • Min-heap: std::priority_queue<int, std::vector<int>, std::greater<int>>, or std::greater<> with pairs.
  • Complexity: push and pop are O(log n), top is O(1), building from n elements is O(n).
  • top() is const: you cannot move the element out of the queue without a copy (C++ has no pop() that returns the value). Work around it by storing pointers or handles, or copy top() and then pop().
  • No iteration and no priority updates. For Dijkstra, push duplicates and skip stale entries when popped.
  • Equal priorities come out in an unspecified order; the queue is not stable. Add a sequence number to the key if order matters.
  • Related algorithms: std::make_heap, std::push_heap, std::pop_heap and std::sort_heap operate on a plain vector if you need access to the elements.
  • Top-k trick: keep a min-heap of size k to track the k largest values of a stream.