优先级队列核心价值

C++标准库中的priority_queue容器适配器提供了一种高效维护优先级数据结构的方式。本文将深入解析其核心特性，并通过实际案例展示其在系统设计和算法优化中的应用。

基础用法解析

#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();
    }
    // 输出：100 40 30 25

    return 0;
}

默认采用std::less比较函数实现最大堆结构，每次取出的都是当前队列中的最大值。

最小堆实现技巧

#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();
    }
    // 输出：25 30 40 100

    return 0;
}

通过指定std::greater比较函数实现最小堆结构，适用于需要优先处理较小值的场景。

自定义类型支持

#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;
}

通过自定义比较函数实现任务调度系统，展示如何根据业务需求定制优先级逻辑。

元素修改技巧

#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);

    // 修改元素后重新插入队列
    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;
}

通过指针包装和重新插入的方式实现元素优先级的动态调整。

进程调度器实战

#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;
}

展示优先级队列在操作系统进程调度中的典型应用，通过动态调整进程执行顺序优化系统性能。

性能基准测试

#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;
}

通过对比测试验证优先级队列在大数据量场景下的性能优势。

常见陷阱与解决方案

1. 直接修改元素
   队列内元素不可变，需通过指针间接修改后重新插入

2. 有序遍历需求
   优先级队列不支持顺序遍历，需逐个弹出处理

3. 内存管理优化
   大对象建议使用智能指针避免拷贝开销

4. 比较函数规范
   自定义比较器必须满足严格弱序要求

priority_queue作为C++标准库的高效数据结构，在任务调度、事件处理、算法优化等场景展现强大能力。掌握其特性与最佳实践，可显著提升系统性能和代码质量。对于更复杂的需求，可结合其他容器实现混合数据结构。