C++ priority_queue Explained
Mastering Heaps in the Standard Template Library
What is a Priority Queue?
Definition: A
priority_queue is a container adapter in the C++ STL
that provides constant time lookup of the largest (or smallest) element. It is typically
implemented as a binary heap.
Basic Usage (Max Heap)
By default, std::priority_queue functions as a Max Heap, meaning the largest element
is always at the "top".
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
// Top element will be 30
std::cout << "Top: " << pq.top() << std::endl;
pq.pop(); // Removes 30
// Top is now 20
std::cout << "New Top: " << pq.top() << std::endl;
return 0;
}Creating a Min Heap
To store the smallest element at the top (useful for algorithms like Dijkstra's), you need to change the comparator.
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
// Top element is now 10 (the smallest)
std::cout << minHeap.top(); Time Complexity
Understanding the cost of operations is crucial for performance optimization.
| Operation | Complexity | Description |
|---|---|---|
push() |
O(log N) | Inserts element and re-balances heap |
pop() |
O(log N) | Removes top element and re-balances |
top() |
O(1) | Accesses the highest priority element |