Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.
This context is similar to a heap
where only the max heap
element can be retrieved (the one at the top in the priority queue
) and elements can be inserted indefinitely.
Priority queues are implemented as container adaptors
, which are classes that use an encapsulated object of a specific container class as its underlying container
, providing a specific set of member functions to access its elements. Elements are popped
from the "back"
of the specific container, which is known as the top
of the priority queue.
The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it must be accessible through random access iterators and it must support the following operations:
Therefore, the standard container class templates vector
can be used. By default, if no container class is specified for a particular priority_queue
class, the standard container class template vector
Support for random access iterators is required to keep a heap structure internally at all times. This is done automatically by the container adaptor by calling the algorithms make_heap
In their implementation in the C++ Standard Template Library, priority queues take three template parameters:
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
Where the template parameters have the following meanings:
- T: Type of the elements.
- Container: Type of the underlying container object used to store and access the elements.
- Compare: Comparison class: A class such that the expression comp(a,b), where comp is an object of this class and a and b are elements of the container, returns true if a is to be placed earlier than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function. This defaults to less<T>, which returns the same as applying the less-than operator (a<b).
The priority_queue object uses this expression when an element is inserted or removed from it (using push or pop, respectively) to grant that the element popped is always the greatest in the priority queue.
In the reference for the priority_queue
member functions, these same names (T
) are assumed for the template parameters.
- Construct priority queue (public member function)
- Test whether container is empty (public member function)
- Return size (public member function)
- Access top element (public member function)
- Insert element (public member function)
- Remove top element (public member function)