C++ 中 "priority_queue" 优先级队列实例详解

1. 什么是优先级队列（Priority Queue）?

优先级队列是一种特殊的队列，它的元素按照一定的优先级进行排序和访问。在 C++ 中，我们可以使用 priority_queue 类来实现优先级队列。

2. priority_queue 类的基本用法

priority_queue 类定义在 <queue> 头文件中。以下是 priority_queue 类的基本用法：

#include <queue>

// 定义优先级队列，元素类型为 int，默认为大顶堆
std::priority_queue<int> pq;

// 向优先级队列中插入元素
pq.push(5);
pq.push(2);
pq.push(10);
pq.push(1);

// 访问优先级队列的顶部元素
int topElement = pq.top();
cout << "Top element: " << topElement << endl;

// 弹出优先级队列的顶部元素
pq.pop();

3. 修改优先级队列为小顶堆

默认情况下，priority_queue 是大顶堆，即元素的顺序按照从大到小进行排列。如果我们希望使用小顶堆，可以通过传入一个自定义的比较函数对象实现。

#include <queue>

// 定义小顶堆的比较函数对象
struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};

// 定义小顶堆优先级队列
std::priority_queue<int, std::vector<int>, Compare> pq;

// 向小顶堆中插入元素
pq.push(5);
pq.push(2);
pq.push(10);
pq.push(1);

// 访问小顶堆的顶部元素
int topElement = pq.top();
cout << "Top element: " << topElement << endl;

// 弹出小顶堆的顶部元素
pq.pop();

4. 复杂类型元素的优先级队列

除了基本数据类型，我们也可以使用自定义的复杂类型作为优先级队列的元素，只需定义一个比较函数即可。

以学生类为例，我们根据学生的分数进行排列：

#include <queue>
#include <string>

// 学生类定义
class Student {
public:
    std::string name;
    int score;

    // 构造函数
    Student(const std::string& n, int s) : name(n), score(s) {}

    // 定义比较函数
    bool operator<(const Student& other) const {
        // 优先按分数从大到小排列
        if (score != other.score) {
            return score > other.score;
        }
        // 分数相同则按姓名的字典序排列
        return name > other.name;
    }
};

// 定义学生类的优先级队列
std::priority_queue<Student> pq;

// 向队列中插入学生对象
pq.push(Student("Alice", 90));
pq.push(Student("Bob", 80));
pq.push(Student("John", 95));

// 访问队列的顶部元素
Student topStudent = pq.top();
cout << "Top student: " << topStudent.name << ", Score: " << topStudent.score << endl;

// 弹出队列的顶部元素
pq.pop();

以上示例演示了如何使用自定义比较函数，将学生对象按照分数从高到低进行排列。

通过以上的说明，你应该能够理解和使用 C++ 中的 priority_queue 类了。记住根据需要选择合适的比较函数对象，并根据实际需求定义自定义的元素类型。