# std::priority_queue

From cppreference.com
< cpp‎ | container

Defined in header `<queue>` |  |
template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; |  |

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided `Compare` can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a `priority_queue` is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

### Template parameters

T | - | The type of the stored elements. The behavior is undefined if `T` is not the same type as `Container::value_type`. (since C++17)

Container

-

The type of the underlying container to use to store the elements. The container must satisfy the requirements of `SequenceContainer`, and its iterators must satisfy the requirements of `RandomAccessIterator`. Additionally, it must provide the following functions with the usual semantics:

- `front()`
- `push_back()`
- `pop_back()`

The standard containers std::vector and std::deque satisfy these requirements.

Compare | - | A `Compare` type providing a strict weak ordering.

### Member types

Member type | Definition
`container_type` | `Container`
`value_compare` (C++17) | `Compare`
`value_type` | `Container::value_type`
`size_type` | `Container::size_type`
`reference` | `Container::reference`
`const_reference` | `Container::const_reference`

### Member functions

(constructor) | constructs the `priority_queue` (public member function)
(destructor) | destructs the `priority_queue` (public member function)
operator= | assigns values to the container adaptor (public member function)

##### Element access

top | accesses the top element (public member function)

##### Capacity

empty | checks whether the underlying container is empty (public member function)
size | returns the number of elements (public member function)

##### Modifiers

push | inserts element and sorts the underlying container (public member function)
emplace (C++11) | constructs element in-place and sorts the underlying container (public member function)
pop | removes the top element (public member function)
swap | swaps the contents (public member function)

### Member objects

Container c | the underlying container (protected member object)
Compare comp | the comparison function object (protected member object)

### Non-member functions

std::swap(std::priority_queue) | specializes the std::swap algorithm (function template)

### Helper classes

std::uses_allocator<std::priority_queue> (C++11) | specializes the std::uses_allocator type trait (function template)

### Example

Run this code

    #include <functional>
    #include <queue>
    #include <vector>
    #include <iostream>

    template<typename T> void print_queue(T& q) {
        while(!q.empty()) {
            std::cout << q.top() << " ";
            q.pop();
        }
        std::cout << '\n';
    }

    int main() {
        std::priority_queue<int> q;

        for(int n : {1,8,5,6,3,4,0,9,7,2})
            q.push(n);

        print_queue(q);

        std::priority_queue<int, std::vector<int>, std::greater<int> > q2;

        for(int n : {1,8,5,6,3,4,0,9,7,2})
            q2.push(n);

        print_queue(q2);

        // Using lambda to compare elements.
        auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
        std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

        for(int n : {1,8,5,6,3,4,0,9,7,2})
            q3.push(n);

        print_queue(q3);

    }

Output:

    9 8 7 6 5 4 3 2 1 0
    0 1 2 3 4 5 6 7 8 9
    8 9 6 7 4 5 2 3 0 1

Retrieved from "http://en.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue&oldid=92077"
Hidden category:

- Pages with unreviewed LWG DR marker