struct priority_queue

这是一个 C++ 中的优先队列数据结构，它可以自动维护队列中元素的优先级，使得每次取出的元素都是当前队列中优先级最高的元素。

优先队列的实现方式有多种，常见的有基于堆的实现和基于红黑树的实现。在 C++ STL 中，优先队列默认使用基于堆的实现。

优先队列支持插入元素、删除队首元素、获取队首元素等操作，时间复杂度为 O(log n)。

相关问题

priority_queue存struct

可以使用priority_queue存储struct，只需要在定义priority_queue时指定比较函数即可。比较函数需要返回bool类型，表示两个元素的优先级大小关系。

例如，定义一个结构体Person，包含姓名和年龄两个成员变量，按照年龄从小到大排序：

struct Person {
    string name;
    int age;
};

struct cmp {
    bool operator() (const Person& a, const Person& b) {
        return a.age > b.age; // 按照年龄从小到大排序
    }
};

priority_queue<Person, vector<Person>, cmp> pq;

priority_queue cmp

### C++ `priority_queue` 自定义比较器用法

在C++标准库中，`std::priority_queue` 默认是一个最大堆，即最大的元素位于顶部。为了改变这一行为或实现更复杂的逻辑，可以自定义比较器。

#### 定义自定义比较器类
通过创建一个小于运算符重载的仿函数（functor），来指定优先级顺序：

struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 创建最小堆
    }
};

此结构体中的操作会使得较小数值具有更高优先级[^1]。

#### 使用自定义比较器初始化 `priority_queue`
当声明 `priority_queue` 时，可以通过模板参数传递该比较器以及底层容器类型（可选）:

#include <queue>
#include <vector>

// 声明一个基于 vector 的最小堆
std::priority_queue<int, std::vector<int>, Compare> minHeap;

上述代码片段展示了如何利用自定义比较器构建一个最小堆而不是默认的最大堆。

对于更加复杂的数据结构比如对象实例，则可以在比较器内部访问成员变量来进行对比判断：

struct Job {
    int id;
    double urgency;

    // 构造函数...
};

struct JobCompare {
    bool operator()(Job* j1, Job* j2) const {
        return j1->urgency < j2->urgency; // 更紧急的任务有更高的优先权
    }
};

int main() {
    std::priority_queue<Job*, std::vector<Job*>, JobCompare> jobQueue;
}

这段例子说明了怎样针对特定应用需求设计合适的比较机制。