C++ Priority Queue
Understanding heap-based data structures in C++
📊 What is a Priority Queue?
A priority queue is a container that provides constant-time access to the largest (or smallest) element. In C++, it's implemented as a max-heap by default, where elements are ordered by priority rather than insertion order.
#include
#include
using namespace std;
int main() {
// Create a max-heap priority queue
priority_queue pq;
// Add elements
pq.push(30);
pq.push(10);
pq.push(20);
// The top element is always the largest
cout << "Top element: " << pq.top() << endl; // Output: 30
return 0;
}
Types of Priority Queues
Max-Heap (Default)
Largest element has highest priority
priority_queue pq; Min-Heap
Smallest element has highest priority
priority_queue, greater> pq; Custom Comparator
Define your own priority rules
auto cmp = [](int a, int b) { return a > b; };
priority_queue, decltype(cmp)> pq(cmp); 🔹 Basic Priority Queue Operations
Priority queues manage elements where the highest (or lowest) priority item is always accessed
first. Implemented as a max-heap by default, the top() function retrieves the largest
element, push() adds an item, and pop() removes the top. It’s ideal for scheduling tasks,
event simulation, or anytime you need repeated access to the extremum. The underlying container is usually a vector
or deque, and operations have logarithmic complexity.
#include
#include
using namespace std;
int main() {
priority_queue pq;
// Adding elements
pq.push(5);
pq.push(2);
pq.push(8);
// Accessing the top element
cout << "Top: " << pq.top() << endl; // 8
// Removing the top element
pq.pop();
cout << "Top after pop: " << pq.top() << endl; // 5
// Check if empty
if (!pq.empty()) {
cout << "Queue has " << pq.size() << " elements" << endl;
}
return 0;
} Output:
Top: 8
Top after pop: 5
Queue has 2 elements
🔹 Min-Heap Priority Queue
A min-heap priority queue reverses the default ordering by using a custom comparator like
std::greater<int>, ensuring the smallest element is always at the top. This is
essential for algorithms such as Dijkstra's shortest path, Prim's minimum spanning tree, and any scenario requiring
repeated extraction of the minimum value. The interface remains unchanged—top(), push(),
and pop() work identically—but the comparison logic is inverted. By understanding both max-heap and
min-heap implementations, you can efficiently solve diverse graph, optimization, and priority-based problems in C++
applications.
#include
#include
#include
using namespace std;
int main() {
// Min-heap priority queue
priority_queue, greater> minHeap;
minHeap.push(30);
minHeap.push(10);
minHeap.push(20);
cout << "Smallest element: " << minHeap.top() << endl; // 10
return 0;
} Output:
Smallest element: 10