What is a priority queue?

It is essentially a heap disguised as a queue, as the priority queue interface only allows elements to be removed from the front and added at the back, making it appear like a queue.

Additionally, the elements within a priority queue are automatically arranged according to their priority. How is this ordering achieved?

By default, priority_queue uses a max-heap to sort elements. This max-heap is represented as a complete binary tree using a vector.

What is a Heap?

A heap is a complete binary tree where each node’s value is not less than (or not greater than) its children’s values. If a parent node’s value is greater than or equal to its children, it is a max-heap. If it is less than or equal to its children, it is a min-heap.

Max-Heap: The root is the largest element.
Min-Heap: The root is the smallest element.

So, when people refer to a max-heap (with the largest element at the heap’s top) or a min-heap (with the smallest element at the heap’s top), they are talking about the ordering of elements in the heap. If you prefer not to implement it yourself, you can use priority_queue, which has the same underlying implementation. Sorting from smallest to largest gives a min-heap, and sorting from largest to smallest gives a max-heap.