priority queue
A priority queue is an abstract data type — a description of behavior, not a specific layout. A plain queue serves items first-in-first-out; a priority queue instead always serves the item with the highest priority next, regardless of when it arrived. Think of a hospital emergency room: the most urgent patient is seen first, not the one who happened to walk in earliest.
Its interface is small: push an item with a priority, and pop (or peek at) the current most-urgent one. Because that is the exact shape a heap excels at, a priority queue is almost always implemented with a binary heap, giving O(log n) push and pop and O(1) peek. It could be backed by other structures — a sorted array, a balanced tree — but the heap is the standard choice because it is fast and needs no pointers.
Keeping the ADT separate from the heap that powers it is the point: you program against 'give me the most urgent item' and let the library pick the structure. In C++ that is std::priority_queue, a max-heap by default. Priority queues are the engine behind Dijkstra's shortest paths, Prim's minimum spanning tree, event-driven simulations, and Huffman coding — anywhere you must repeatedly grab the current best or smallest thing.
std::priority_queue<int> pq; // max-heap by default
pq.push(3);
pq.push(9);
pq.push(5);
while (!pq.empty()) {
std::cout << pq.top() << ' '; // prints 9 5 3
pq.pop();
}std::priority_queue — a max-heap behind a queue-like interface.
C++'s std::priority_queue is a max-heap by default; pass std::greater (or negate keys) to get a min-priority-queue.