std::priority_queue in C++: Priority-Based Element Processing
What is std::priority_queue in C++: Priority-Based Element Processing? std::priority_queue is a container adapter that provides constant time lookup ($O(1)$) of the highest (or lowest) priority element using a binary heap (usually...
How does std::priority_queue work, what is its underlying data structure, and how do you configure custom ordering?
Explanation & In-Depth Details
- Max-Heap (Default): `std::priority_queue<T>`
- Min-Heap: `std::priority_queue<T, std::vector<T>, std::greater<T>>`
```text
BINARY MAX-HEAP CONCEPT:
[95 (top)]
/ \
[70] [80]
/ \ /
[30] [50] [60]
```
2. Time Complexities:
- `top()`: $O(1)$
- `push()`: $O(\log N)$
- `pop()`: $O(\log N)$
Code Example
#include <iostream>
#include <queue>
#include <vector>
#include <string>
struct Patient {
std::string name;
int triagePriority; // Higher number = higher medical urgency
bool operator<(const Patient& other) const {
return triagePriority < other.triagePriority; // Defines Max-Heap
}
};
int main() {
std::priority_queue<Patient> erQueue;
erQueue.push({"John (Sprained Ankle)", 2});
erQueue.push({"Sarah (Cardiac Arrest)", 10});
erQueue.push({"Mike (Fever)", 4});
std::cout << "Emergency Room Patient Processing Order:\n";
while (!erQueue.empty()) {
const auto& p = erQueue.top();
std::cout << " - Treating: " << p.name << " [Priority: " << p.triagePriority << "]\n";
erQueue.pop();
}
return 0;
}Interview Question & Tips
A: It uses binary heap algorithms from `<algorithm>`: `std::push_heap`, `std::pop_heap`, and `std::make_heap` on an underlying `std::vector`.
Q: How do you create a Min-Heap priority queue of integers in C++?
A: `std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;`
Best Practices
• Remember that `top()` returns a const reference; modify items only by popping and re-inserting.
• Always verify `!pq.empty()` before accessing `.top()` or calling `.pop()`.
This study reference for std::priority_queue in C++: Priority-Based Element Processing is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation: