Core Value of Priority Queue
The <span>priority_queue</span> container adapter in the C++ Standard Library provides an efficient way to maintain a priority data structure. This article will delve into its core features and demonstrate its applications in system design and algorithm optimization through practical examples.
Basic Usage Analysis
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// Output: 100 40 30 25
return 0;
}By default, it uses the <span>std::less</span> comparison function to implement a max-heap structure, where the maximum value in the queue is retrieved each time.
Min-Heap Implementation Techniques
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(30);
min_pq.push(100);
min_pq.push(25);
min_pq.push(40);
while (!min_pq.empty()) {
std::cout << min_pq.top() << " ";
min_pq.pop();
}
// Output: 25 30 40 100
return 0;
}By specifying the <span>std::greater</span> comparison function, a min-heap structure is implemented, suitable for scenarios where smaller values need to be prioritized.
Support for Custom Types
#include <iostream>
#include <queue>
#include <string>
struct Task {
int priority;
std::string name;
Task(int p, std::string n) : priority(p), name(std::move(n)) {}
};
struct CompareTask {
bool operator()(const Task& t1, const Task& t2) {
return t1.priority < t2.priority;
}
};
int main() {
std::priority_queue<Task, std::vector<Task>, CompareTask> task_queue;
task_queue.emplace(3, "Write report");
task_queue.emplace(1, "Fix critical bug");
task_queue.emplace(2, "Prepare presentation");
while (!task_queue.empty()) {
const Task& task = task_queue.top();
std::cout << "Priority: " << task.priority << ", Task: " << task.name << std::endl;
task_queue.pop();
}
return 0;
}By implementing a custom comparison function, a task scheduling system is demonstrated, showcasing how to customize priority logic based on business needs.
Element Modification Techniques
#include <iostream>
#include <queue>
#include <memory>
struct Item {
int priority;
std::string name;
Item(int p, std::string n) : priority(p), name(std::move(n)) {}
};
struct CompareItem {
bool operator()(const std::shared_ptr<Item>& i1, const std::shared_ptr<Item>& i2) {
return i1->priority < i2->priority;
}
};
int main() {
std::priority_queue<std::shared_ptr<Item>, std::vector<std::shared_ptr<Item>>, CompareItem> item_queue;
auto item1 = std::make_shared<Item>(2, "Item 1");
auto item2 = std::make_shared<Item>(1, "Item 2");
item_queue.push(item1);
item_queue.push(item2);
// Modify element and reinsert into the queue
item2->priority = 3;
item_queue.push(item2);
while (!item_queue.empty()) {
auto item = item_queue.top();
std::cout << "Priority: " << item->priority << ", Name: " << item->name << std::endl;
item_queue.pop();
}
return 0;
}Dynamic adjustment of element priority is achieved through pointer wrapping and reinsertion.
Process Scheduler Practical Example
#include <iostream>
#include <queue>
#include <string>
#include <iomanip>
struct Process {
int priority;
std::string name;
int burst_time;
Process(int p, std::string n, int bt) : priority(p), name(std::move(n)), burst_time(bt) {}
};
struct CompareProcess {
bool operator()(const Process& p1, const Process& p2) {
return p1.priority < p2.priority;
}
};
class Scheduler {
private:
std::priority_queue<Process, std::vector<Process>, CompareProcess> process_queue;
public:
void add_process(int priority, const std::string& name, int burst_time) {
process_queue.emplace(priority, name, burst_time);
}
void run() {
int total_time = 0;
std::cout << std::left << std::setw(15) << "Process" << std::setw(10) << "Priority"
<< std::setw(15) << "Burst Time" << std::setw(15) << "Start Time" << std::endl;
while (!process_queue.empty()) {
Process current_process = process_queue.top();
process_queue.pop();
std::cout << std::left << std::setw(15) << current_process.name
<< std::setw(10) << current_process.priority
<< std::setw(15) << current_process.burst_time
<< std::setw(15) << total_time << std::endl;
total_time += current_process.burst_time;
}
}
};
int main() {
Scheduler scheduler;
scheduler.add_process(3, "Process A", 5);
scheduler.add_process(1, "Process B", 3);
scheduler.add_process(4, "Process C", 2);
scheduler.add_process(2, "Process D", 4);
scheduler.run();
return 0;
}This demonstrates a typical application of priority queues in operating system process scheduling, optimizing system performance by dynamically adjusting the execution order of processes.
Performance Benchmark Testing
#include <iostream>
#include <queue>
#include <vector>
#include <chrono>
#include <random>
const int NUM_ELEMENTS = 1000000;
void benchmark_priority_queue() {
std::priority_queue<int> pq;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < NUM_ELEMENTS; ++i) {
pq.push(i);
}
for (int i = 0; i < NUM_ELEMENTS; ++i) {
pq.pop();
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "priority_queue time: " << diff.count() << " seconds" << std::endl;
}
void benchmark_sorted_vector() {
std::vector<int> vec;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < NUM_ELEMENTS; ++i) {
vec.push_back(i);
std::push_heap(vec.begin(), vec.end());
}
for (int i = 0; i < NUM_ELEMENTS; ++i) {
std::pop_heap(vec.begin(), vec.end());
vec.pop_back();
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Sorted vector time: " << diff.count() << " seconds" << std::endl;
}
int main() {
benchmark_priority_queue();
benchmark_sorted_vector();
return 0;
}This validates the performance advantages of priority queues in scenarios with large data volumes through comparative testing.
Common Pitfalls and Solutions
- 1. Directly Modifying Elements Elements in the queue are immutable; modifications must be done indirectly through pointers and reinserted.
- 2. Ordered Traversal Requirements Priority queues do not support sequential traversal; elements must be popped one by one for processing.
- 3. Memory Management Optimization For large objects, it is recommended to use smart pointers to avoid copy overhead.
- 4. Comparison Function Specifications Custom comparators must satisfy strict weak ordering requirements.
<span>priority_queue</span> is an efficient data structure in the C++ Standard Library, demonstrating powerful capabilities in task scheduling, event handling, and algorithm optimization. Mastering its features and best practices can significantly enhance system performance and code quality. For more complex requirements, it can be combined with other containers to implement hybrid data structures.
If you like my article, please give me a thumbs up! Thank you!