std::priority_queue<T> is a container adapter that serves elements by priority instead of insertion order. By default, the element that compares largest comes out first, so it's a max-heap with a familiar push/top/pop interface. The adapter wraps a sequence container (a std::vector<T> by default) and exposes only the operations a heap needs. This chapter covers what a heap is, the small API the adapter offers, how to flip it into a min-heap, how to use custom comparators for objects, the typical workloads (task scheduling, top-K problems, Dijkstra), and the costs to be aware of.

A heap is a binary tree with one rule: every parent compares at least as large as its children. The root is therefore the maximum of the whole tree, accessible in O(1). Inserts and removals cost O(log n) because they have to walk one path from the root to a leaf to restore the heap property.

The diagram shows the conceptual tree of a max-heap holding 100, 80, 60, 50, 20, 30. The root (100) is the maximum. Every node is greater than or equal to its children. The heap doesn't sort the whole array; it only maintains the parent-child ordering, which is enough to find the maximum cheaply.

The actual storage is a flat array, not a tree of node objects. Index i's children sit at 2i+1 and 2i+2, and its parent at (i-1)/2. That layout is cache-friendly, requires no extra pointers, and lets std::vector<T> serve as the backing container. The library takes care of every index calculation; callers just push and pop.

The declaration from <queue>:

Three template parameters: the element type, the container (default std::vector<T>), and the comparator (default std::less<T>, which gives the max-heap behavior). The comparator answers the question "is a lower priority than b?" The element for which the comparator says "I am less than nothing else" ends up at the top.

The adapter forwards a small set of operations to the underlying vector. Everything the vector could do (indexing, iteration, range insert) is hidden by design. A reader looking at std::priority_queue<T> can see at a glance that the code processes elements by priority and nothing else.

The full interface is six member functions:

That's the entire surface area. No iteration, no random access, no find, no way to inspect anything except the top.

A first example: a shipping queue where each order has a numeric priority. The carrier wants to ship the highest-priority order first, regardless of when it was placed.

Output:

The elements come out from highest to lowest, with duplicates appearing as many times as they were pushed. The fifth push (the second 8) didn't replace the first 8; both are in the heap and both come out in turn.

The while (!empty()) loop is the common "drain the queue" idiom. top() reads the highest, then pop() removes it. The split between top() (read) and pop() (remove) exists for exception safety, described below.

Pushing all 5 elements is 5 O(log n) operations, so O(n log n) total. Building a heap from an existing range can be done in O(n) using std::make_heap directly on a vector, but the priority queue adapter doesn't expose that path; for the build-once-from-a-range case, use the lower-level algorithms.

pop() removes the top element and returns void. That looks awkward because the natural call site is "give me the top and remove it." Why two calls instead of one?

Exception safety. If pop() returned the top by value, the return path would copy or move the element out of the heap. If that copy or move throws (a std::bad_alloc from a deep copy, an exception from a move constructor), the heap has already removed the element from its storage but hasn't successfully handed it to the caller. The element is lost. By splitting the operation into top() (read) and pop() (remove), the caller gets to choose: read first, then remove only if the read succeeded.

The standard pattern, when the value is needed after removal:

Output:

The const_cast is needed because top() returns a const T& from the adapter, even though the underlying vector's element is non-const. Moving from a const reference would copy; the cast unlocks the move. Most code doesn't need this dance because it just reads the top by value:

For lightweight types like int or pointers, just take a copy and call pop(). The optimization with std::move matters only for heavy types (large strings, owning vectors, complex objects).

Calling top() or pop() on an empty priority queue is undefined behavior. Guard with empty() or use the while (!empty()) loop.

The default comparator is std::less<T>, which gives "largest first." For "smallest first", pass std::greater<T> as the third template parameter. The second template parameter (the container) must be specified too, because parameters are positional.

Output:

Same elements, opposite order. std::greater<int> returns true when its first argument is greater than its second, which inverts the heap's notion of priority. Now the smallest element is the "highest priority" and sits at the top.

A common workload that fits a min-heap perfectly: a "top-K largest" tracker. To find the K largest values in a stream of N elements, keep a min-heap of size K. When a new value is bigger than the smallest one in the heap (top()), pop the smallest and push the new value. At the end, the heap holds the K largest. The work is O(N log K), which beats sorting (O(N log N)) when K is small.

Output:

The min-heap keeps the answer set bounded at 3 entries. Every incoming value is compared against the smallest of the current top three; if it's larger, the smallest is evicted. Draining the heap at the end gives the answers from smallest to largest. To print them largest first, copy them into a vector and reverse, or use a regular max-heap and pop them all (at the cost of holding the full N elements).

A similar trick with a max-heap gives the K smallest values. The pattern is the same; flip the comparator and the comparison direction.

For element types that don't have a sensible operator<, supply a comparator. Two options: overload operator< on the type itself, or pass a function-object type as the third template parameter.

Overloading operator<

If the element type "owns" the comparison, overload operator< and rely on the default std::less. This works well when the order is intrinsic to the type.

Output:

ORD-4 ships first because it has the highest priority. The comparator says "tasks with smaller priority values are less than tasks with larger ones," so the larger ones end up on top.

Comparator as a Functor

When the type already has an operator< for some other purpose, or when the same type needs to be ordered different ways in different queues, supply a functor (a struct with operator()) as the third template parameter.

Output:

The ByUrgency functor returns true when a is less urgent than b (i.e., a.promisedDays > b.promisedDays). Less-urgent tasks sink, more-urgent ones float to the top. The orders come out by ascending promised days.

The functor approach also works with lambdas, using decltype to spell the priority queue's type:

Output:

The lambda has an unnameable type, so decltype(byUrgency) is needed to spell the queue's third template parameter. The constructor takes the lambda as an argument because the queue needs an instance of the comparator (lambdas with no captures became default-constructible in C++20, which lets the constructor argument be dropped).

A common pitfall with custom comparators: write the comparison from the perspective of "which one is lower priority?" The element for which the comparator says "I am less than everything else" sits at the top of the heap. Flipping the direction by mistake produces a queue that drains in the opposite order from the intended one. When the output is wrong, swap < and > and try again.

The default container is std::vector<T>. The heap algorithms (std::push_heap, std::pop_heap, std::make_heap underneath the adapter) need random-access iteration plus efficient push and pop at the back, so the choices are std::vector or std::deque. A std::list does not work, because it doesn't support random access.

Output:

There are few reasons to pick std::deque over std::vector. The vector's contiguous storage is more cache-friendly for the index-arithmetic walks that heap operations do. The deque's only advantage is that pushing to the back never reallocates the whole storage, which can matter when individual elements are large and the cost of a single vector reallocation copy is undesirable. For the common case, leave the container at its default.

Workloads that fit std::priority_queue:

Task Scheduling

Any system that processes items by priority instead of arrival order. Order fulfillment ranked by customer tier, alerts ranked by severity, jobs ranked by deadline. The priority queue keeps the next-to-process element at the top and reorders automatically as new tasks come in.

Dijkstra's Shortest Path

The classic textbook use. The algorithm visits the closest unvisited node next, where "closest" means smallest known distance from the source. A min-heap keyed by distance gives the next-to-visit node in O(log n) per step. The full algorithm runs in O((V + E) log V) using a binary heap, which is the standard pre-Fibonacci-heap analysis.

Output:

The min-heap is keyed on std::pair<int,int>, where the first element is the distance. The default lexicographic ordering on pairs compares by first element first, which is what's needed. The "stale entry" check (if (d > dist[u]) continue;) is needed because the heap doesn't support decrease-key: when a shorter path is found, the algorithm pushes a new entry instead of updating the old one, and the stale older entry has to be skipped when it surfaces.

Top-K Problems

Already shown in the min-heap section: keep a bounded heap, evict the worst entry when a better one arrives. This pattern shows up in trending-products dashboards, leaderboard maintenance, and any "show me the best N" feature where N is small relative to the total stream.

K-Way Merge

To merge K sorted lists, push the head of each list into a min-heap. The smallest head sits at the top; pop it, take the next element from its source list, and push that. The output stream is the K lists in sorted order. The cost is O(N log K), where N is the total element count.

Output:

The heap never holds more than K entries (one per active list), so each push and pop is O(log K). The total work is O(N log K), which beats merging the lists pairwise (O(N log K) with K-1 merges, each linear).

Two costs to be aware of when picking std::priority_queue over alternatives:

No decrease-key. Once an element is in the heap, its priority can't be updated. The Dijkstra example above shows the workaround: push a new entry and skip stale older ones when they surface. For very dense graphs, this can inflate the queue size to O(E) instead of O(V), with proportional log factor in the cost. A pairing heap or a Fibonacci heap supports decrease-key in better-than-log time, but neither is in the C++ standard library, so pushing duplicates and skipping stale entries is the usual approach.

No iteration, no removal of arbitrary elements. The adapter exposes only the top. To inspect or remove a non-top element, the heap has to be drained into another container, which costs O(n log n). When iteration matters, use a std::multiset (ordered, supports iteration, slower constant factor) or a std::vector plus the std::*_heap algorithms directly (more control, more code).

Allocation behavior. Each push may trigger a vector reallocation if capacity runs out. For a workload with a known maximum size, calling reserve on the underlying vector before constructing the priority queue avoids repeated reallocations, but the adapter doesn't expose reserve directly; the workaround is to construct the priority queue from a std::vector<T> with the desired capacity already set:

The two-argument constructor takes the comparator and the underlying container. Passing a reserved vector hands the adapter a buffer that's already big enough.

The three adapters (stack, queue, priority_queue) share the same skeleton: an underlying container, a small forwarding interface, no iteration, pop() returns void. They differ in the order they hand elements out:

Pick based on the access pattern the code actually needs. For "the most recent thing added," a stack. For "the next thing in arrival order," a queue. For "the highest-priority thing regardless of arrival," a priority queue.

A small running example: a customer-support routing system. Tickets arrive with a priority (1-5, higher is more urgent), and the dispatcher should hand them to the next available agent in priority order. When two tickets share a priority, the older one goes first.

Output:

Tickets come out by priority, with ties broken by arrival order. The two p=5 tickets ship in arrival order ("Cannot log in" arrived before "Site is down"), then the three p=3 tickets in arrival order, then the lone p=1. The comparator handles the tiebreaker without any extra data structures.

Compile with g++ -std=c++17 file.cpp. Every API used here works back to C++11; structured bindings (used in earlier examples) are the only C++17-specific feature.