A priority queue is an abstract data type (ADT) that maintains a set of elements according to a priority algorithm (usually a maximum or minimum element).
They’re usually implemented with heaps (min, max), which are able to maintain the required sorted quality that priority queues use.
Language-specific
In C++
In C++, priority queues are provided in the STL. It’s functionally speaking implemented as a heap, without ways to invalidate the heap. As a result of this, it’s not possible to iterate through the structure.
It’s possible to construct with particular arguments:
- Within the angle brackets, we can specify the data type (usually this is all that’s included), container type, and criteria (
std::greater<T>orstd::less<T>). By default, it constructs a max priority queue.std::greater<T>gives us a min priority queue.
- It’s also possible to construct with iterators, especially with vector iterators.
std::priority_queue pq (vec.begin(), vec.end(), function)- Note that the function can also include lambdas. The lambda must be enclosed in
decltype().
Useful methods:
push()inserts an element and validates the heap.pop()removes the top element.top()returns the top element as a const.