69
The priority_queue in the C++ Standard Template Library (STL) is a container adapter that provides a convenient way to manage a collection of elements with priority.
It is based on the heap data structure, typically a max-heap by default, where the largest element is given the highest priority. You can customize it to function as a min-heap as well.
Key Features of priority_queue
- Max-Heap by Default: The largest element has the highest priority.
- Min-Heap Option: Custom comparators can be used to make it behave as a min-heap.
- Efficient Operations: Provides push, pop, and top operations with logarithmic complexity.
Basic Syntax
#include <queue> using namespace std; priority_queue<Type> pq; // Max-heap (default) priority_queue<Type, vector<Type>, Comparator> pq; // Min-heap with custom comparator
Let’s explore the priority_queue with examples of both max-heap and min-heap configurations.
1. Basic Max-Heap priority_queue
By default, priority_queue in C++ is a max-heap, where the largest element has the highest priority.
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Declare a max-heap priority_queue
priority_queue<int> pq;
// Insert elements
pq.push(10);
pq.push(20);
pq.push(5);
// Display top element (largest element)
cout << "Top element: " << pq.top() << endl;
// Remove elements and display them
cout << "Elements in priority order: ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Top element: 20 Elements in priority order: 20 10 5
2. Using priority_queue as a Min-Heap
To use priority_queue as a min-heap, specify greater<Type> as the comparator.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// Declare a min-heap priority_queue
priority_queue<int, vector<int>, greater<int>> pq;
// Insert elements
pq.push(10);
pq.push(20);
pq.push(5);
// Display top element (smallest element)
cout << "Top element: " << pq.top() << endl;
// Remove elements and display them
cout << "Elements in priority order: ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Top element: 5 Elements in priority order: 5 10 20
3. Custom Comparator with priority_queue
You can use a custom comparator for complex sorting requirements, such as creating a max-heap or min-heap for pairs.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Custom comparator for min-heap of pairs based on the second element
struct Compare {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
};
int main() {
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
// Insert elements (pairs)
pq.push({1, 50});
pq.push({2, 30});
pq.push({3, 40});
// Display top element (pair with smallest second value)
cout << "Top element: {" << pq.top().first << ", " << pq.top().second << "}" << endl;
// Remove elements and display them
cout << "Elements in priority order based on second value: ";
while (!pq.empty()) {
auto elem = pq.top();
cout << "{" << elem.first << ", " << elem.second << "} ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Top element: {2, 30}
Elements in priority order based on second value: {2, 30} {3, 40} {1, 50}
4. Checking if priority_queue is Empty
The empty function checks if the priority_queue is empty.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
// Check if the priority queue is empty
if (pq.empty()) {
cout << "The priority queue is empty." << endl;
}
// Insert an element and check again
pq.push(10);
if (!pq.empty()) {
cout << "The priority queue is not empty." << endl;
}
return 0;
}
Output:
The priority queue is empty. The priority queue is not empty.
5. Retrieving the Size of a priority_queue
Use the size function to get the number of elements in the priority_queue.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
// Insert elements
pq.push(10);
pq.push(20);
pq.push(5);
// Display the size of the priority queue
cout << "Size of the priority queue: " << pq.size() << endl;
return 0;
}
Output:
Size of the priority queue: 3
6. Using priority_queue with Custom Objects
You can use priority_queue with custom objects by providing a custom comparator to define their priority.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
// Custom structure for tasks
struct Task {
string name;
int priority;
// Custom comparator for min-heap based on priority
bool operator<(const Task &other) const {
return priority > other.priority;
}
};
int main() {
priority_queue<Task> pq;
// Insert tasks
pq.push({"Task 1", 3});
pq.push({"Task 2", 1});
pq.push({"Task 3", 2});
// Display tasks in priority order
cout << "Tasks in priority order:" << endl;
while (!pq.empty()) {
Task t = pq.top();
cout << t.name << " (Priority: " << t.priority << ")" << endl;
pq.pop();
}
return 0;
}
Output:
Tasks in priority order: Task 2 (Priority: 1) Task 3 (Priority: 2) Task 1 (Priority: 3)
7. Modifying a priority_queue with Existing Elements
Since priority_queue doesn’t support random access, you’ll need to empty it, modify elements, and reinsert them if you want to change existing elements.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> pq;
// Insert elements
pq.push(10);
pq.push(20);
pq.push(5);
// Modify elements by removing and reinserting them
vector<int> elements;
while (!pq.empty()) {
int val = pq.top();
pq.pop();
elements.push_back(val * 2); // Double each element
}
// Reinsert modified elements
for (int val : elements) {
pq.push(val);
}
// Display modified elements in priority order
cout << "Modified elements in priority order: ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Modified elements in priority order: 40 20 10
8. Using priority_queue with Strings
You can use priority_queue to manage strings based on lexicographical order.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
// Max-heap for strings
priority_queue<string> pq;
// Insert strings
pq.push("apple");
pq.push("orange");
pq.push("banana");
// Display strings in priority order (lexicographical order)
cout << "Strings in priority order: ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Strings in priority order: orange banana apple
9. Using a priority_queue for Sorting an Array
You can use a priority_queue to sort an array by inserting all elements and removing them in priority order.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {10, 3, 15, 7, 8};
// Min-heap to sort in ascending order
priority_queue<int, vector<int>, greater<int>> pq;
// Insert elements into the priority queue
for (int num : arr) {
pq.push(num);
}
// Extract sorted elements
cout
<< "Sorted elements: ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
Output:
Sorted elements: 3 7 8 10 15
Summary Table of priority_queue Operations
| Operation | Code Example | Description |
|---|---|---|
| Initialize Max-Heap | priority_queue<int> pq; | Initializes a max-heap (default) |
| Initialize Min-Heap | priority_queue<int, vector<int>, greater<int>> pq; | Initializes a min-heap |
| Insert Element | pq.push(10); | Inserts an element |
| Access Top Element | pq.top(); | Accesses the highest priority element |
| Remove Top Element | pq.pop(); | Removes the highest priority element |
| Check if Empty | pq.empty(); | Checks if the priority_queue is empty |
| Get Size | pq.size(); | Returns the number of elements |
| Custom Comparator | priority_queue<Type, vector<Type>, Compare> pq; | Initializes with a custom comparator |
| Clear All Elements | Use pq.pop() in a loop | Clears all elements manually |
| Use with Custom Objects | struct Task {…}; and priority_queue<Task> pq; | Use a struct with custom comparator |
Complete Example
This example demonstrates initializing a max-heap and a min-heap, inserting elements, accessing and removing elements, and using a custom comparator.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Custom comparator for min-heap of pairs based on the second element
struct Compare {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
};
int main() {
// Max-heap
priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(20);
maxHeap.push(5);
cout << "Max-Heap: ";
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
cout << endl;
// Min-heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
cout << "Min-Heap: ";
while (!minHeap.empty()) {
cout << minHeap.top() << " ";
minHeap.pop();
}
cout << endl;
// Min-heap with custom comparator for pairs
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pairPQ;
pairPQ.push({1, 50});
pairPQ.push({2, 30});
pairPQ.push({3, 40});
cout << "Custom Comparator Min-Heap for Pairs: ";
while (!pairPQ.empty()) {
auto elem = pairPQ.top();
cout << "{" << elem.first << ", " << elem.second << "} ";
pairPQ.pop();
}
cout << endl;
return 0;
}
Sample Output:
Max-Heap: 20 10 5
Min-Heap: 5 10 20
Custom Comparator Min-Heap for Pairs: {2, 30} {3, 40} {1, 50}
Key Takeaways
- priority_queue is a heap-based container that defaults to a max-heap.
- Custom comparators make it versatile for both max-heap and min-heap use cases.
- Useful for scenarios where elements need to be processed in a priority order, such as implementing queues with custom priorities, sorting, or maintaining top elements.