Standard Template Library (STL)
std::priority_queue
Max-heap by default — O(log n) push/pop, O(1) top access
Interview: One of the most-used containers in coding interviews — Dijkstra, top-K problems, merge K sorted lists
std::priority_queue
std::priority_queue is a container adaptor that provides O(log n) insertion and O(log n) removal of the highest-priority element. The highest-priority element can be peeked in O(1). By default it's a max-heap — the largest element is at the top. It uses std::vector as its underlying container.
Min-Heap
To get a min-heap, use greater<T> comparator: priority_queue<int, vector<int>, greater<int>> minHeap;. This is extremely common in Dijkstra's algorithm and top-K minimum problems.
Custom Comparators
For custom types, provide a comparator via a lambda or functor: auto cmp = [](pair<int,int> a, pair<int,int> b) { return a.second > b.second; }; priority_queue<...> pq(cmp); — min-heap by second element.
Operations Summary
| Operation | Complexity | Notes |
|---|---|---|
| push() | O(log n) | Inserts and sifts up |
| pop() | O(log n) | Removes top, sifts down |
| top() | O(1) | Read max/min without removing |
| size()/empty() | O(1) | Metadata access |
Interview Corner
Q: How do you find the K largest elements in an array using a priority queue?
A: Use a min-heap of size K. Iterate through elements: push each into the heap. If the heap exceeds size K, pop the minimum (the smallest of the current K candidates). At the end, the heap contains the K largest elements. Time: O(n log K), Space: O(K). This is better than sorting O(n log n) when K << n.
Q: How does Dijkstra's algorithm use a priority queue?
A: Dijkstra's uses a min-heap (min priority queue) of (distance, node) pairs. Initially push (0, source). While heap is not empty: pop the minimum-distance node, skip if already visited, mark as visited, push all unvisited neighbors with updated distances. The heap ensures we always process the closest unvisited node first — greedy correctness. Time: O((V + E) log V) with a binary heap.
Common Pitfalls
- Default is max-heap: Many algorithms need a min-heap. Remember: use
greater<T>for min-heap — a common interview mistake is using the wrong direction. - No iteration: std::priority_queue does not support iteration. If you need to inspect all elements, use
std::make_heapon a vector instead.
Best Practices
- Use
emplace()instead ofpush()for complex types to construct in-place and avoid copying. - For custom types, define the comparator clearly — test which direction gives you the heap behavior you need before running with it.