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.
#include <queue> std::priority_queue<int> pq; pq.push(3); pq.push(9); pq.push(5); pq.top(); // 9
Try it
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.
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
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::lessputs 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>>, orstd::greater<>with pairs. - Complexity:
pushandpopare O(log n),topis 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 nopop()that returns the value). Work around it by storing pointers or handles, or copytop()and thenpop().- 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_heapandstd::sort_heapoperate 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.