In the world of C++ data structures, the priority queue stands out as a powerful tool for managing elements based on their priority. This heap-based container adaptor provides efficient access to the highest (or lowest) priority element, making it invaluable for various applications, from task scheduling to graph algorithms.
Understanding Priority Queues in C++
A priority queue in C++ is a container adaptor that provides constant time lookup of the largest (by default) or smallest element, at the cost of logarithmic insertion and extraction. It's implemented using a heap, which is a specialized tree-based data structure.
🔑 Key Features:
- Elements are stored in a way that the highest priority element is always at the top.
- Insertion and deletion operations take O(log n) time.
- Accessing the top element is an O(1) operation.
Let's dive into how to use priority queues in C++ with practical examples.
Creating a Priority Queue
To use a priority queue in C++, you need to include the <queue> header. Here's a simple example of creating a max heap priority queue:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "Top element: " << pq.top() << std::endl;
return 0;
}
Output:
Top element: 30
In this example, we create a priority queue of integers. By default, C++ uses a max heap, so the largest element is always at the top.
Creating a Min Heap Priority Queue
To create a min heap priority queue, we need to use the greater<> comparator:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(10);
min_pq.push(30);
min_pq.push(20);
std::cout << "Top element: " << min_pq.top() << std::endl;
return 0;
}
Output:
Top element: 10
Here, we've created a min heap priority queue where the smallest element is always at the top.
Basic Operations on Priority Queue
Let's explore the basic operations you can perform on a priority queue:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// Pushing elements
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
std::cout << "Size of priority queue: " << pq.size() << std::endl;
// Accessing top element
std::cout << "Top element: " << pq.top() << std::endl;
// Removing top element
pq.pop();
std::cout << "After popping, new top: " << pq.top() << std::endl;
// Checking if empty
std::cout << "Is priority queue empty? " << (pq.empty() ? "Yes" : "No") << std::endl;
return 0;
}
Output:
Size of priority queue: 4
Top element: 100
After popping, new top: 40
Is priority queue empty? No
🔍 Note: The pop() function removes the top element but doesn't return it. If you need the value, make sure to call top() before pop().
Priority Queue with Custom Objects
Priority queues aren't limited to built-in types. You can use them with custom objects by defining a comparison function. Let's create a priority queue of students sorted by their grades:
#include <iostream>
#include <queue>
#include <string>
struct Student {
std::string name;
int grade;
Student(std::string n, int g) : name(n), grade(g) {}
};
struct CompareStudent {
bool operator()(const Student& s1, const Student& s2) {
return s1.grade < s2.grade;
}
};
int main() {
std::priority_queue<Student, std::vector<Student>, CompareStudent> student_pq;
student_pq.push(Student("Alice", 85));
student_pq.push(Student("Bob", 92));
student_pq.push(Student("Charlie", 78));
student_pq.push(Student("David", 95));
std::cout << "Top student: " << student_pq.top().name
<< " with grade " << student_pq.top().grade << std::endl;
return 0;
}
Output:
Top student: David with grade 95
In this example, we've created a custom Student struct and a CompareStudent functor to define how students should be ordered in the priority queue.
Implementing a Task Scheduler
Let's use a priority queue to implement a simple task scheduler. Each task will have a priority and a description:
#include <iostream>
#include <queue>
#include <string>
struct Task {
int priority;
std::string description;
Task(int p, std::string d) : priority(p), description(d) {}
};
struct CompareTask {
bool operator()(const Task& t1, const Task& t2) {
return t1.priority < t2.priority;
}
};
class TaskScheduler {
private:
std::priority_queue<Task, std::vector<Task>, CompareTask> tasks;
public:
void addTask(int priority, const std::string& description) {
tasks.push(Task(priority, description));
}
void executeHighestPriorityTask() {
if (!tasks.empty()) {
std::cout << "Executing task: " << tasks.top().description
<< " (Priority: " << tasks.top().priority << ")" << std::endl;
tasks.pop();
} else {
std::cout << "No tasks to execute." << std::endl;
}
}
};
int main() {
TaskScheduler scheduler;
scheduler.addTask(3, "Send email");
scheduler.addTask(1, "File report");
scheduler.addTask(2, "Call client");
scheduler.addTask(5, "Urgent meeting");
for (int i = 0; i < 5; ++i) {
scheduler.executeHighestPriorityTask();
}
return 0;
}
Output:
Executing task: Urgent meeting (Priority: 5)
Executing task: Send email (Priority: 3)
Executing task: Call client (Priority: 2)
Executing task: File report (Priority: 1)
No tasks to execute.
This task scheduler uses a priority queue to always execute the highest priority task first.
Performance Considerations
🚀 Performance characteristics of priority queues:
| Operation | Time Complexity |
|---|---|
| Push | O(log n) |
| Pop | O(log n) |
| Top | O(1) |
| Empty | O(1) |
| Size | O(1) |
While priority queues offer excellent performance for their intended use cases, it's important to consider alternatives for different scenarios:
- If you need fast insertion and deletion at both ends, consider
std::deque. - For sorted data with fast insertion at any position,
std::setmight be more appropriate. - If you need to frequently access elements by index,
std::vectorcould be a better choice.
Advanced Usage: Dijkstra's Algorithm
Priority queues are often used in graph algorithms. Let's implement Dijkstra's algorithm for finding the shortest path in a weighted graph using a priority queue:
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
typedef std::pair<int, int> pii;
class Graph {
int V;
std::vector<std::vector<pii>> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v, int w) {
adj[u].push_back(std::make_pair(v, w));
adj[v].push_back(std::make_pair(u, w));
}
void shortestPath(int src) {
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
std::vector<int> dist(V, std::numeric_limits<int>::max());
pq.push(std::make_pair(0, src));
dist[src] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto i = adj[u].begin(); i != adj[u].end(); ++i) {
int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(std::make_pair(dist[v], v));
}
}
}
std::cout << "Vertex Distance from Source\n";
for (int i = 0; i < V; ++i)
std::cout << i << "\t\t" << dist[i] << "\n";
}
};
int main() {
Graph g(9);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.shortestPath(0);
return 0;
}
Output:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
In this implementation, we use a priority queue to always process the vertex with the smallest known distance first, which is the core idea of Dijkstra's algorithm.
Conclusion
Priority queues in C++ offer a powerful way to manage elements based on their priority. Whether you're implementing a task scheduler, optimizing graph algorithms, or solving complex programming challenges, the priority queue data structure provides an efficient solution for priority-based operations.
Remember these key points:
- Priority queues in C++ are implemented as heap-based container adaptors.
- By default, C++ priority queues are max heaps, but can be configured as min heaps.
- Custom objects can be used with priority queues by defining appropriate comparison functions.
- Priority queues are particularly useful in scenarios where you always need quick access to the highest (or lowest) priority element.
By mastering priority queues, you'll add a valuable tool to your C++ programming toolkit, enabling you to solve a wide range of problems more efficiently and elegantly.
